Yes. As long as the new feat is a valid feat for your current character, you can retrain the old feat and replace it with the new feat.
For example, if you are a 3rd-level rogue who took Improved Initiative at 1st level, you can retrain that feat and replace it with Weapon Focus. Even though Weapon Focus has a prerequisite of "base attack bonus +1" (which means you couldn't take it as a 1st-level rogue), it is a valid feat for your current level (3rd), and is therefore a valid choice for retraining.
(Note: Likewise, the fighter class ability to retrain fighter bonus feats does not require you to meet all of the new feat's prerequisites at the level you originally gained the feat.)
No.
The retraining rules say, "If retraining a class level means you no longer qualify for a feat, prestige class, or other ability you have, you can't use that feat, prestige class, or ability until you meet the qualifications again." Therefore, if you retrain out of the base class and that causes you to no longer meet the requirements of the prestige class, you no longer have access to the class features from that prestige class, and therefore can't use that prestige class to meet the requirements of anything (including itself).
Update 10/16/13: In any case, you cannot use rule elements from a prestige class to meet the requirements of that prestige class.
Update 10/16/13: New ruling: You cannot use retraining to replace a base class level with a prestige class level.
