I can recomment rimuhosting (http://rimuhosting.com) for a VPS setup- that means you can install/run what you like. They will setup most stuff if you put what you want into your order. Support, the few times I've needed it, has been great.
I don't have Django on that setup, yet- just got lighttpd running so I can switch off apache before cranking up mysql. Derek
