3 years ago my wife and I stayed at a Best Western on Sussex Gardens, near Paddington Station. It was fine and ran about 90 pounds/night. It is a little bit of a ride to the theater districy, but the cab rides are part of the London experience. We took in 2 shows and toured around a good bit without feeling we were in a bad location.
Paddington Station was just around the corner, and the buses came by regularly as well. You can get around in London without breaking the bank if you spend a little time planning and use the public transportation.
There are plenty of areas that would work equally as well, and I might try elsewhere on my next trip. But I would not hesitate to go back to that area. Beware that some of the hotels on Sussex Gardens were nicer than others, and I think if you try to get a bargain basement rate, you might be disappointed.
Try Londontown.com for a hotel search engine.
Good luck,
Sarge