No that is not a solution.
If they swapped the public key they can read the message being sent back (it is encrypted with their public key), then encrypt it again with the real public key.
The only solution is to use another channel to authenticate the other's key, be it GPG's web of trust, or any other imperfect way (phone call, physically meeting, ...)
First, Agree on a reply latency -- say, 1 day.
Then, instead of simply replying to a message, you have an irritating four-step process:
1. Wait until one day after you received the message.
2. Send a digest of the message and your public key.
3. Wait another day.
4. Send the message itself.
All that sending would be using PGP.
The receiver must make sure that the delays for receiving the digest and the reply body are what the expect. This method requires a MITM to either anticipate what the message is or introduce an extra day of latency, which the receiving would notice.
You don't ask for your message back, you ask for the message Snowden sent again. The MITM-party can't have that, assuming that Snowden started with your correct public key.
Yes. The solution is to make him repeat his original message as well, which couldn't have been intercepted because it was encrypted with our own key.