I get this same message about once a week since I frequently use my Linode VPS as a proxy for my web traffic, but it's never lasted for more than a half hour or so. I've always wondered why their heuristics only seem to notice me so infrequently. Do you get it consistently?
Yes, I have never been able to access Google from my Slicehost VPN IIRC. I also used a Linode VPN for a while and got the message infrequently with the possibility to enter a CAPTCHA to complete my request.