When I try to send my public key on T-Mobile USA using a Nexus One (with Cyanogen), I get the following error message back from the carrier:
"Unable to send message to 1917xxxxxx. Please try again without a symbol in the text"
Perhaps you need to Base64 encode the data you are sending?