Well, in my case it was the Fast CGI that fasthosts.co.uk use.
I finally got them to look at the .htaccess rewrite requirements for SilverStripe and they admitted that their system only allows simple .htaccess commands.
They basically can't support SilverStrip, joomla, wordpress or anything else that requires rewrites, so I'm guessing in my case that the install crashed out and incorrectly reported the PHP 5 required message.
Moved to another hosting company that doesn't use Fast CGI - works a treat now!
I guess I need to be carefull when customers already have a hosting plan to check that their system will indeed support the proposed CMS, although I was pretty surprised that with fasthosts claiming to be the UK's #1 ISP, they don't support pretty much 99% of all the current web design packages.