This happens if another user bids for the same block reward but pays a higher gas price. In that case, your transaction will likely end up in the same block *after* that user's transaction.

Currenly, it looks like users pay between 3 and 4 Gwei for a transaction (you can look this up on EtherScan, but hopefully we'll have a dashboard soon that shows some stats about that.).

This means that if you want your transaction to likely succeed, you should set a gas price of 5-6 Gwei.