Ok. The support guys at the hosting company informed me that the "AllowOverride All" change had been made.
I re-ran the install.php file (after manually adding in the "memory" tweak borriej suggested to the .htaccess file) - choosing to let the installer re-install the .htaccess and _config.php files (as it has realised that a previous install attempt had been made).
Unfortunately the "installing" page did it's usual thing, getting as far as "Creating /var/www/vhosts/silverstripetest.co.uk/httpdocs/.htaccess" and then seems to go no further.
I have checked the server's error log and although I performed the install (or at least tried to) at 5.12pm... the error log is last modified at 5.01pm
[Tue May 04 17:01:03 2010] [notice] Apache/2.2.3 (CentOS) configured -- resuming normal operations
So, the previously highlighted error is no longer showing up... but unfortunately no other error is showing either.
I really am unsure as what to do next. Sean, if I email it across (so it's not publicly in the forum) could I send the FTP details for the domain - so that someone at SilverStripe could freshly upload the appropriate files and witness the install browser screen for themselves? I'd feel so bloody stupid, if I'd somehow been misuploading something or not getting something's permissions quite right.