When they mention the amount of disk space available, that may or may not include the virtual server itself. For example, looking at the linode page, the free space is the space left after the distribution is installed.
2. Uptime. Providers that claim 99.999% or whatever uptime are simply lying. It's probably the uptime of their network connection, but not individual server - I've had 3 different VPS's over the past two years (Verio, JVDS and Spry), and every one of them has at least once experienced a server problem where it was down for several hours.
3. Proprietary things. Whatch out for provider trying to lock you into their way of doing things. This may be a complicated xinetd/qmail setup that works well with their GUI panel (which you may not care about). Once you get used to their way of doing things, it would be hard to move to another provider who will probably have a different setup.
4. Watch out for the price. The vast majority of the hosting companies out there operate as Ponzi schemes - their main source of revenue is the setup and pre-payment fees, but the monthly fee alone isn't enough to sustain their costs. This makes them very eager to keep signing up new customers and not to work hard on retaining them.
5. Few hosting providers will upgrade their servers, it's just too much trouble. So if you got a FreeBSD 4.3 or RedHat 7.2, it will probably stay this way despite of what the sales guy may tell you.
6. You don't know what hardware they are using. It is trivial to patch the kernel so that dmesg always reports it's a 2.4GHz Xeon whereas it's really a PII.
7. Most hosting companies don't like to reveal their inner workings. You can most of the time guess whether it is a FreeBSD jail, a Linux UML (those usually list memory limits as part of the price), a Linux VServer (not a lot of those yet, but it's the future most likely) or a proprietary solution like the ViaVerio crap. What this means is that you don't know what security and reliability measures they have in place, don't ever assume anything.
8. AUP. A more restrictive AUP is a good thing IMHO. Providers with liberal AUP's are usually winking that they like to host porn. You probably don't want to be on the same machine with a porn site because they will eat all your CPU. Some providers prefer porn customers because they are easy to deal with, always pay on time and don't like to draw attention. Then other providers don't host porn because they consider it immoral.
9. Make sure that the IP's you get have not been previously spoiled by a spammer. You will find out sooner or later when your e-mails sent from the VPS bounce.
Well that's about all I can think of right now...