The photoproduction of omega mesons on nuclei has been investigated using the Crystal Barrel/TAPS experiment at the ELSA tagged photon facility in Bonn. The aim is to study possible in-medium modifications of the omega meson via the reaction gamma + A --> omega + X --> pi(0)gamma + X('). Results obtained for Nb are compared to a reference measurement on a LH2 target. While for recoiling, long-lived mesons (pi(0), eta, and eta;(')), which decay outside of the nucleus, a difference in the line shape for the two data samples is not observed, we find a significant enhancement towards lower masses for omega mesons produced on the Nb target. For momenta less than 500 MeV/c an in-medium omega meson mass of M(medium) = [722(+4)(-4)(stat)+35-5(syst)] MeV/c(2) has been deduced at an estimated average nuclear density of 0.6rho(0).