My only advice is that if you are struggling to get web2py running on your host, don't fight it, switch.
Webfaction comes up a lot as a great provider. If you are at all thinking about cloud, I say "go for it". Amazon, RackSpace and Linode are great options.