Michael Roberson, the guy who founded MP3.com and Lindows, has another venture called MP3Tunes. This service allows you to upload and store you music collection to their servers. You can then access your music via virtually any device: web browser, PDA, EVDO laptop, GPRS phone, and now even TiVo. The MP3Tunes application for TiVo will work for Series 2 and above, but is still in beta stage.
Another interesting note about the service is that it will automatically select the correct file type and bit rate based on the device you are accessing the service with. For instance when accessing from a GPRS phone, it will stream in 32kbps and select a compatible file type based on what your brand of phone supports. I have not had a chance to try it myself, but it looks pretty slick. Check out the video demo for more info.