I agree that you should get very musical upstream components... be it something tubed or... a Scott Nixon non-oversampling DAC (
www.scott-nixon.com). Non-oversampling dacs sound very musical, natural and coherent, and I chose to keep my Scott Nixon over a highly modded ART DI/O (which is a giant killer of a dac). The standard version costs $250 and should do great. If you want a bit of tube goodness and the flexibility to try different tubes, then the TubeDac adds a tube to the standard dac and is $400. The Panasonic S47 DVD-A player ($99) and Toshiba 4960 universal player ($149) are said to do quite well as transports. So, you can have a very good and musical front end within your $500 budget.
A tube pre would be a good idea as well. I have a tube pre as well as a Tube Dac. First off, I know that your Rotel amp has balanced inputs... but is it a true balanced circuit? Often a balanced connector is connected to a single-ended circuit... perhaps you can do a bit of research on the 'net on this.
If you Rotel does not have a balanced circuit, then you will have many more preamps to choose from as balanced outputs are not common. By the way, if you find a preamp with balanced outputs... make sure it has a balanced circuit as well!
How you require a remote on your preamp? If so, that will further limit your ability to get a great sounding pre for $700, even used.
If you don't need a remote or can live without balanced outputs, the Eastern Electric Minimax tube pre is terrific. Their Minimax cd player is also said to sound excellent (though it is a bit above your budget).
Finally, do plan on getting a good power conditioner somewhere down the road. Your cd player / dac / preamp -- and especially your ears -- will certainly thank you for it. There is a lot of snake oil in the power conditioner market. I myself favor balanced power as the benefits of balanced power on delicate electronics are scientifically proven and are listed in the U.S. national electrical code. You can read up about this at
http://www.b-p-t.com/ The now discontinued BPT BP-1 Jr would do well for source components -- check on
www.audiogon.com for a used one. I like the Blue Circle Music Ring balanced power supply. Transcendent Sound makes a similar product for just $399 (though you will need to use an extension cord as it only has 1 outlet).
Good luck!