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:
Shouldn't the ger be able to to prepare the para aduma?
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:
If a ger (convert) is considered like a newborn are they tahor?
No, they are not Tahor, by Rabbinic decree.
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?
No, since your first premise was incorrect.
Normally the problem associated with preparing the para aduma is the person who makes it must be tahor before doing so.
Not 100% correct. He was usually a Tvul Yom. See Rambam הלכות פרה אדומה פרק ג