OK - figured it out - it was nothing to do with the php, but thought I'd put the solution down in case anyone else was having the same problem. The .htaccess rules weren't quite right. Once they were amended as follows they worked fine. I also had to put a slash in front of all my relative links in order for them to work:
RewriteRule ^company/([A-Za-z0-9-]+)\.php$ company.php?PageName=$1 [NC,L]
RewriteRule ^product/([A-Za-z0-9-]+)\.php$ product.php?CatName=$1 [NC,L]