well, it depends on how you're actually DOING your camera at the moment, You don't really say. Sounds like a classic example of gimbal lock to me. The way I've had my camera set up for quite some time seems to be the most widespread and convenient usage ( disregarding quaternion solutions ). I have 3 orthogonal vectors representing the Orthonormal base of the camera's transformation system. Essentially these can be plugged directly into a 3x3 matrix to compose the rotation part of the camera's transformation. When rotating I rotate two of the camera normals around the target normal. Every now and again you have to re-normalise to ensure its still orthogonal.
This has its advantages because you always have ready access to the three normals that represent the cameras view direction, the cameras 'up' direction and the 'side' direction of the camera. You can use these for a multitude of things, such as panning and dollying the camera, using the 'up' and 'side' vectors to construct billboards, etc etc.
Theres quite a few good tutorials on the net about the best way to construct your camera class, I'd suggest a bit of googling