I can recommend Positive Internet, apart from being a good host with excellent support they were helpful enough to make configuration changes on their server just to get Magento working well. I recommend Positive Internet to my clients, and am in the process of working on 2 Magento based sites hosted on their servers.
If you sign up for a shared hosting account, make sure you request PHP5 for the default PHP.
I have a reseller account with www.unitedhosting.co.uk but they don’t offer mcrypt so just a word of warning if you’re considering them
I posted in their forum asking whether Magento would run and they said it would - only to find out shortly afterwards mcrypt was not supported.
...a quick helpdesk ticket later and they fixed up the server so it could run Magento, in a very short space of time. I’ve not had service like that since I was with Rochen (indeed, it was one of the guys at Rochen that recommended me to go with unitedhosting.co.uk).
I normally host my sites with Nativespace but will probably be moving over to UH.
I’ve just switched to United Hosting. I was totally fed up with Fasthosts and they did not support Magento, nor “the other open source cart” particularly well. United are cheaper, you get more “out of the box” and tech support is good.
So far no problems with them at all. They also told me that although they didn’t currently have a set up that supported Magento, they don’t see it as a problem when I need it (which is not yet as I’m waiting until 31st March).
Actually, it’s only ‘down for maintenance’ as I had a new site design to put in, which should be back up and looking shiny later today once I’ve smoothed off the rough edges. I probably also shouldn’t be playing with Magento 1.0 myself just yet either