Modification of TiO2 with metal oxide nanoclusters such as FeOx, NiOx has been shown to be a promising approach to the design of new photocatalysts with visible light absorption and improved electron-hole separation. To study further the factors that determine the photocatalytic properties of structures of this type, we present in this paper a first principles density functional theory (DFT) investigation of TiO2 rutile(110) and anatase(001) modified with PbO and PbO2 nanoclusters, with Pb2+ and Pb4+ oxidation states. This allows us to unravel the effect of the Pb oxidation state on the photocatalytic properties of PbOx-modified TiO2. The nanoclusters adsorb strongly at all TiO2 surfaces, creating new Pb-O and Ti-O interfacial bonds. Modification with PbO and PbO2 nanoclusters introduces new states in the original band gap of rutile and anatase. However the oxidation state of Pb has a dramatic impact on the nature of the modifications of the band edges of TiO2 and on the electron-hole separation mechanism. PbO nanocluster modification leads to an upwards shift of the valence band which reduces the band gap and upon photoexcitation results in hole localisation on the PbO nanocluster and electron localisation on the surface. By contrast, for PbO2 nanocluster modification the hole will be localised on the TiO2 surface and the electron on the nanocluster, thus giving rise to two different band gap reduction and electron-hole separation mechanisms. We find no crystal structure sensitivity, with both rutile and anatase surfaces showing similar properties upon modification with PbOx. In summary the photocatalytic properties of heterostructures of TiO2 with oxide nanoclusters can be tuned by oxidation state of the modifying metal oxide, with the possibility of a reduced band gap causing visible light activation and a reduction in charge carrier recombination.