pQd covered it all really well, so im not really adding too much. One thing I would recommend is speaking to some current customers - also check for any bad reviews online.
Check out the network. Who are the upstream providers (make sure they have are more than one!) and who are the upstream providers? What kind of bandwidth do they have coming into the building (DS3, Fiber, Etc) and are these connections coming in through physically diverse paths? How much bandwidth do they have access to? The more connected they are, the better off you are when it comes to data transport between you and your clients, employees, etc. You would be surprised at the number of colocation facilities operating on a single connection.
I agree with #pQd - ask about bandwidth billing - make sure you know what your getting into.