When you are seeing the name next to the address, it is a manual process of associating a text string with that address. It's that simple. They have a metadata field that they can add to any address. This process is not via an API or across the entire Ethereum network. Each blockchain explorer (etherscan, etherchain, and live.ether.camp) do it differently and have different accounts labeled.
As you don't seem to take my answer as correct, here is EtherScan's answer:
Submit links to your official site under the comments section and Verify the Source code of your contract.. and then wait :-)
In fact, after answering that question I wanted to make sure it was correct, so I commented on MyEtherWallet's donation account address. A couple days later, Matt @ EtherScan upvoted my comment and now we have a tag.
Furthermore, not all addresses on Shapeshift are listed. I just looked at one of my accounts and the unique address I sent the ETH to is not labeled as Shapeshift.
However, the address that ETH was sent from (in this case, I didn't the correct amount of ETH so it was returned to me) is labeled: http://etherscan.io/address/0x120a270bbc009644e35f0bb6ab13f95b8199c4ad
This seems to be their Ethereum hot wallet (although this is most likely changing due to the security breach on 4/7) and so it can be easily labeled. I looked around and couldn't find any other addresses labeled as Shapeshift, so I think that your assumption that every address ShapeShift generates in labeled Shapeshift is wrong.
Best Answer
An Ethereum address is 40 hex characters. Some interfaces expect the address to be prepended with a "0x" and some interfaces will not accept this. myetherwallet prepends the "0x". Try to paste the address without the "0x".