If a ger (convert) is considered like a newborn are they tahor? If this is the case then if we were able to find a red cow then shouldn't the ger be able to to prepare the para aduma? Normally the problem associated with preparing the para aduma is the person who makes it must be tahor before doing so.
To answer the 2nd half of your question:
No. A Para Aduma can only be prepared by a Cohen. (A Ger cannot be a Cohen.)
The Rambam הלכות פרה אדומה פרק א הלכה י"ג says that any Cohen can be used.
From Rashi (and Sifsei Chachamim) in the Chumash it appears - based in the Sifri (ספרי קכג) - that he holds that only a Cohen Gadol or his Segan Cohen Gadol can prepeare the Para Aduma.
It's actually dependent on a disagreement between Bet Shammai and Bet Hillel.
As we learned in Psachim 92a:
"Somebody who coverts on Erev Pessach: Bet Shammai says he can go to the Mikveh and eat Korban Pessach at night."
So Bet shammai would consider him a Tvul-Yom - and as such he would be allowed to be involved in preparing the Para Aduma. (See Mass. Para 3:7 that they davka used a Tvul Yom.)
"Bet Hillel says that a convert has the status of somebody who touched a grave". He therefor has to wait 7 days before he becomes a Tvul Yom (and permitted to make the Para Aduma) and until that night to be fully Tahor.
(This is actually a Rabbinic decree, so that the Ger doesn't say in future years "my first year as a Jew I touched a grave in the morning and that night ate Korban Pessach, so why should this year be different".)
Since we usually Pasken like Bet Hillel, so the answer to your questions would be:
No, they are not Tahor, by Rabbinic decree.
No, since your first premise was incorrect.
Not 100% correct. He was usually a Tvul Yom. See Rambam הלכות פרה אדומה פרק ג