These are integrated addresses we implemented in May/June.  It's a combination of standard address and payment id in one encoded string for convenience.
simplewallet now has a new command "integrated_address" to perform a conversion both ways and can seamlessly send coins to both type of addresses as well as gui wallet.

Until pools upgrade their daemons/wallets up to the last version, you may withdraw first to your wallet, then transfer to the exchange.
Please make sure you have the latest version.