I'd say the most important thing is to stand out, paid advertising is (in my opinion) a waste of money for the most part, there are so many social networks that offer free advertising etc... Be sure your product is unique, with vps this is a tough thing to come by, but you could also specialize in something such as ddos handling, streaming, cdn or whichever you are good at, if clients want something you are good at they will take a vps from you. It's like being a good webdesigner that just happens to be a webhosting reseller. Location is also very important, price is not so important if the product is good, don't go for $1 vps, you won't make any money unless you have thousands of vm's running.