That's because # is seen as the start of a fragment identifier and confuses the parser.
You can take the easy-way as Stretch suggested but you should be aware that q is the last query parameter in your URL. Therefore, it might be better to fix the URL and extract the query parameters in a safer way:
<?php
$url = "http://www.16start.com/results.php?cof=GALT:#FFFFFF;GL:1;DIV:#FFFFFF;FORID:1&q=search";
// Replace # with its HTML entity:
$url = str_replace('#', "%23", $url);
// Extract the query part from the URL
$query = parse_url($url, PHP_URL_QUERY);
// From here on you could prepend the new url
$newUrl = "http://www.newURL.com/results.php?" . $query;
var_dump($newUrl);
// Or you can even go further and convert the query part into an array
parse_str($query, $params);
var_dump($params);
?>
Output
string 'http://www.newURL.com/results.php?cof=GALT:%23FFFFFF;GL:1;DIV:%23FFFFFF;FORID:1&q=search' (length=88)
array
'cof' => string 'GALT:#FFFFFF;GL:1;DIV:#FFFFFF;FORID:1' (length=37)
'q' => string 'search' (length=6)
Update
After your comments, it seems that the URL is not available as a string in your script and you want to get it from the browser.
The bad news is that PHP will not receive the fragment part (everything after the #), because it is not sent to the server. You can verify this if you check the network tab in the Development tools of your browser F12.
In this case, you'll have to host a page at http://www.16start.com/results.php that contains some client-side JavaScript for parsing the fragment and redirecting the user.