Hi Cider.
Have you had the chance to check for DC offset on your amps?
Do you have any paperwork with the jukebox? I would be wary of manufacturer power output claims, a genuine 250W per channel running flat out would put your windows through in a domestic room size. I would like to see a schematic if you have one just out of interest.
A lot of the advertised power output claims are made with misleading measurements and certain amp destruction if you attempted it yourself. One way to check. When you are in there, note the transformer primary fuse rating and work out how many watts can get into the power supply. It can't put out more wattage than it can get in. I assume you know about discharging capacitors before going near them. As I say, valve amps have step up transformers and very high voltages around the place. Be careful with it.
Speaker sensitivity is a far more relevant figure to be looking at over peak power handling. Google your speakers and see if you can find figures for them. Theres a good explaination of it here...
http://stereos.about.com/od/stereoscience/a/amppower.htm
I have a diy stereo chipamp using two LM1875s that puts out all of 20W per channel in my "best" system. It's feeding a pair of Bib speakers and that can go too loud for a reasonable sized UK front room but still sound stunning with only moderately efficient CSS FR125S drivers.
These are Bibs.....
http://www.zillaspeak.com/bib-pics.asp
Dead easy first build and a superb sounding speaker. Must be against the back wall, preferably in the room corners. Placement is very important with them.
If you have some spare time there is a very informative site for all things hifi including building your own stuff here....
http://myweb.tiscali.co.uk/nuukspot/decdun/
Check out the "gainclone" pages on there and have a peep at the Arcam A60 modification article. If you can poke about in boilers and solder you can build far better sounding amps and replace the ones in the juke box for not that much cash. Pair that to a suitable speaker design that you both like the size and styling of and work from there. Everyone's a winner.
John