I had trouble getting a CC payment to work with another small VPS host, and they let me pay in cash (literal currency through international mail), but maybe that doesn't count since I was an existing customer they were familiar with, not a new sign-up. But if you're trying to run stuff on VPS's and you don't have any existing hosting relationships and you're trying to pay with BTC, that sounds odd.
