My storyline for C-3PO in TPM was:

1) He's on Trade Federation ship, everything is the same until...

2) In the scene, where Nute Gunray landed in Theed and says "ah, victory!" I imagined there would be perfect place to put TC (or 3PO). Now, he's appointed by Gunray to accompany the queen.

3) Qui-Gon and Obi-Wan free the queen with her handmaidens and 3PO goes with them to Tatooine and Coruscant.

In conclusion, at the end of TPM Trade Federation is defeated, Maul is dead, and C-3PO serves now Padme.

The idea of Trade Federation 3PO would be good if you redub Gunray with alien voice. He would translate Gunray's lines to Amidala and the rest of the Naboo folk.

By the way, hilts of Obi-Wan's TPM lightsaber is almost the same as Qui-Gons. The only difference are the little spikes at the end of Kenobi's hilt.