i've waited about 90 minutes before for a single confirmation. it doesn't happen often, though. sometimes i get 2-3 confirmations within only a few minutes. but those times where a single confirmation takes over an hour -- very frustrating.
What I've seen happen is that an output spends unconfirmed inputs. So, even thought the transaction paid the correct fee, the underlying inputs didn't. So, those inputs are talking longer to confirm which slows down the outputs that spent them. I've seen this a few times spending from Coinbase. I think they need to clean up there implementation and spend older inputs. Perhaps they just aren't keeping enough BTC in their hot wallet which is causing this, but that is just supposition.
sometimes if you watch for the next block, though, it literally takes an hour or more for the next block to be found. so it isn't about unconfirmed inputs.