Sometimes you want to keep your opponent guessing where you want to castle. So when they move their pawns forward on the queenside you can castle on the kingside, then the pawn move can sometimes be a lost move. Another reason why I don't castle is when I try to pretend to castle kingside, then wait for my opponent to castle kingside, then castle queenside myself. This works against players that I know are very slow positional players, because it forces them to be more attacking which gets them out of their comfort zone. Also when queens are traded off, castling is usually not nessecary and probably better not to castle because in the endgame the king is better in the center.
When not to castle as soon as possible?

I play gambits,I almost always castle as soon as I can...almost.Since checkmate leaves no weakness in its wake, king safety dominates all considerations. If the center is going to open up,you must castle before your king gets stuck on its start square, and getting it to safety will consume too much time. Others have mentioned that castling can be delayed,or dispensed with,if the Queens comes off AND neither side has developed much, I agree. Furthermore, if you choose to castle,care must be taken that you don't castle into an attack (i.e. into open files where your opponent has more pieces arrayed. Also castling is a development move,rooks come to the center, and if that center is open there is a ready path to the enemy king. Play alot of 1.e4 e5 games and you'll get a feel for when and where you should castle.I usually count an 1.e4 gambit game, where my opponent delays castling, as a win.On the other hand, if you get a lead in development and castle first, and the center opens,throw the kitchen sink at your opponent, you will almost always over run him.

I just watched a Chess Mood video on opening principles and it confirmed my long held suspicion that castling early in the opening can be bad advice. An example given is the Stafford Gambit:
Example of when not castling could be a good idea: