Using Exchange Management Shell to generate a CSR

We've just installed a new Exchange 2007 Server. Mail Flow is working fine. OWA is working fine after imporing the old certificate from the former Exchange 2003 server (Also the root CA) which is still in place, but exchange 2003 is not being used. The issue arises when Outlook 2007 is used as it displays a certificate error. By selecting "Yes" to proceed all is well, but I would like to eliminate this window from popping up. The original certificate was purchased and generated via CSR through Network Solutions. After doing some research I found that it may be best to have Network Solutions reissue the certificate by generating a new CSR using the Exchange Management Shell. I did so using the following command:
New-ExchangeCertificate -GenerateRequest -DomainName mail.company.com,autodiscover.company.com,server1 -Friendlyname mail.company.com -PrivateKeyExportable:$true -Path c:\certreq.txt
The command seemed to work properly, however when I go to submit the CSR to Network Solutions The site fails to accept it saying "Invalid Organization Name" which it is trying to get from the CSR. All spelling in the command was correct. Am I dong something wrong or is it possible that Network Solutions is not capable of generating a certificate from a CSR generated by the Exchange 2007 Management Shell? I'll assume it's me and any advice would be greatly appreciated. Again, Everything works except for the Certificate Error window that pops up only for people using Outlook 2007. I does not seem to effect Outlook 2003. Thanks!