I use http://www.nexcess.net/ it magento works both on there shared and higher plans I use a vps but I had a shared which had magento on it most of it is pre-installed and its not a bad price for there mini shared
Yup, it appears their servers block Magento because it is on the Economy Hosting plan. I really am starting to not like GoDaddy.
Another reason to hate godaddy!
Suggestion: HawkHost is my choice of hosting