a nice big fat backbone helps alot, other than that everything TheBush said. Support is huge. I'd look for a 1-800 number, some sort of sign of downtime/uptime stats. (maybe a forum with power outages posted) if a colocenter has no problems it's too new.

I would also research it on other forums get some reviews from other people that host their servers there.