Why can I not add relationships?
You've correctly isolated the problem to your Bluehost server configuration - and also found that their shared hosting may not be up to your needs!  You may want to get a VPS (I like Linode and Koumbit), or you may want to find shared hosting that can support CiviCRM (like CiviHosting).  Your performance problems will only get worse as you increase the size of your database.

But back to your problem - check out this post to troubleshoot.  My guess is that Bluehost has mod_security or some php.ini setting that's causing an AJAX call to fail.  This page will help you identify exactly what's failing.  Note that if you're looking to move to another host anyway, this may not be worth your aggravation!