<p>I know Hostmonster allows Python. Has anyone successfully run Django on there? Any problems? </p>

Well, if it support Python, you might be able to run Django using a FastCGI setup, as described here:
FastCGI Docs
. If it supports mod_python (which I guess it's what you mean), then sure, you can install it using the steps listed here:
ModPython docs