Because an exchange is always, to some extend, a lending system. Two people exchanging stuff have to accept the idea that one of them will have to "pay" first and wait a bit until the other one pays his part. It can never be simultaneous.
Well.. except between cryptocurrencies perhaps?
It seems to me that 2 bitcoin-based cryptocurrencies could be exchanged atomically by each understanding enough about the other's blockchain to do some sort of multisignature scripted transaction which either succeeds completely or fails completely.
Indeed. I think that's the kind of things you could do with smart-contracts.