I recently got a low cost server from Joe's Datacenter (http://www.joesdatacenter.com) in Kansas, I always like paying under the $50/month for a server (I know I'm cheap...) and found their pricing starting at $35/month for a full on box very nice!
The delivery took about 24 hours and recently I needed support which was also available and Sam did a re-install for me (but installed Centos instead of Ubuntu, was 4am though by them) to get the server back online quickly after I installed a package (cassandra db) which didn't work out very well...
I know many hosting companies have a policy of installing new hard drives when reusing servers recently decommissioned, this doesn't seem to be the policy at Joe's though and the server arrived with a Western Digital WDC WD2500YD-01NVB1 drive (personally I prefer Seagate) and so far it's been in power on mode for 28 369 hours or 1 182.04167 days or 3.32 years which doesn't inspire much confidence... Currently their packages don't provide RAID so backup... backup... backup...
The servers connected directly to a Brocade switch and doing a traceroute outbound from Joe's seems to run out via gigabit links to Hurricane Electric, Cogentco and a connection to the Kansas City Internet Exchange. You can grab their test file download from http://www.joesdatacenter.com/10MB.zip
Joe's also have a live webcam up and running of the colocation section:
So far the server and network stability have been flawless, support available, upgrading sales support is just useless... but at the end of the day if your looking for a cheap box Joe's could be the answer for your requirements!