Can I change an encryption key used without decrypting first I'm looking to solve for a little challenge I have in regards to changing the encryption on a message with asymmetric keys. I'd love to be able to swap the encryption to a different key in memory and without going via the plain text.

So clear text -> encrypted text with first key -> double encrypted text -> encrypted text with second key

I have a vague recollection that it can be done but the Googles are not being forthcoming. I'm far from an expert on this and my preferred implementation would be done in C#.

Thanks in advance.
It's important to define what you want and why. For example, if the server doing the transformation does not hold the secret key of the first kind, then this is "proxy re-encryption". However, if it does hold it, then the question is why not decrypt first. From a security perspective it doesn't matter, and sometimes not from an efficiency perspective as well. 

If you are using ElGamal variant, then you can do this quite easily and it's actually more efficient than decrypting and encrypting. Given key pair $pk_2=h_1$; $sk=x_1$ and $pk_2=h_2$; $sk_2=x_2$ and given $c_1=(u,v)=(g^r \cdot m, h_1^r )$ you can compute $c_2=(u, v^{x_2/x_1})$. Check out why this works yourself...