I made an iPhone game (tower defense) where everything used std:vectors until I ran into performance problems. And lo and behold they could all be solved with using data structures for which the necessary operations where less expensive. The changes were quite easy to make since the containers use a common interface.
The real gotcha is that the vast majority of containers are still vectors, since the operations on them didn't show up in profiling. So I guess yeah create some gameplay and optimize your bottlenecks not your lack of Data structure fun.
In the most important case it was sets.
There was a collision detection routine that took up too much time because checking membership for vectors is not constant time. The sets/vectors were very small though, low double digits, but once you do stuff 30 times per second for a couple a hundred objects it can get slow. (only on the iPhone though, in the simulator everything was good)
For the general world representation I used a static grid, as the object size was very homogenous, so a quad tree would have been overkill.
The real gotcha is that the vast majority of containers are still vectors, since the operations on them didn't show up in profiling. So I guess yeah create some gameplay and optimize your bottlenecks not your lack of Data structure fun.