For backgrounds, I sometimes start with google sketchup!
Sounds daft but to get the perspective, layout, and "feel" of a space it sometimes helps to mock it up in 3D first.
That means I can then choose a "real" camera angle that suits the angle of my character sprites, and even move interesting items into the edges of the shot.
From here I can then output a basic line render and take it into something like flash and go from there.
I tend to hand draw over all the lines as it gives it a looser feel, and start by blocking everything out in grey scale, to give a little sense of the solid edges in a room.
My time-lapse video below shows the next stage which is going from my grey scale base artwork to a fully coloured, lit and detailed background. I prefer to work in flash because of the options that vector artwork gives you and it means all my assets are in one place.
If you watch in in 1080p you can see that although its all vector artwork, you can get those textures, smudges and blurs that look like Photoshop work. Now and again I use photoshop on the exported png's if I need some special texture work on-top, but its rare these days.
http://youtu.be/gPQlDUVUJqo?list=PLfsiC3OLVf-5sx9vCG70nryBds...