Brian from Coinbase here. Sorry you experienced delays! There have been some issues in the past that we are working to improve. Coinbase sends a high volume of bitcoin transactions (often in parallel across many machines), and as a result we sometimes encounters issues that are uncommon elsewhere. In this case, I believe the root of the issue was around spending coins where the inputs were not in a block yet. We broadcast a large number of transactions, and sometimes other nodes receive them out of order (the transaction that spends the change could arrive before the transaction that generated the change). The official client, bitcoind, had an issue (unclear whether it was a bug, or intended) where a transaction in the orphan pool that got connected up (it's input transaction finally arrived) did not subsequently get relayed to the rest of the network like a regular transaction. We've been chatting with Gavin about this to see what solutions could make it into a near term release.
An issue like this could cause it to not be relayed to most/many miners, which is why it would take a long time to make it into a block.
As a short term fix we manually push transactions to certainwell connected nodes like blockchain.info to ensure they are well propagated. Thanks for bearing with us as we continue improving things. Experiences like this are definitely not what we strive for. Hope the explanation helps!