Windows Mobile 6.1: Can't access internal site via https

Whe have several Motorola Symbols (don't remember the exact model) running Windows Mobile 6.1 They are used for entering data in the field, and then at the end of shift the employees come in and "sync" them via an application which utilizes web services. We recently renewed our SSL certificate, and since then we've been unable to get them to sync over https.

Since the application wasn't giving good error message, I decided to see if I could load the page in IE which produces one of three error sitations (and it appears to be device dependant which one you get):

1. Some hand helds just display a gray box (i.e. they don't load anything)
2. some return a message saying "Cannot find 'https://<server>/<dir>/<file>' Make sure the path or Internet address is correct."
3. finally some say "The page cannot be displayed because the Web site cannot be authenticated."

In trying to understand the situation better, I've noticed that:

• If I change https to http, they can always load the page
• If I revert to the old certificate, they work
• We renewed three certificates all with a new CA; if I try one of the other two it works
  • the problem server is running IIS 6 under Windows Server 2003 Standard edition Service Pack 2
  • Working server 1 is running IIS 6 under Windows Server 2003 Standard Edition Service Pack 2
  • Working Server 2 is running IIS 7 under Windows Server 2008 R2 Standard Service Pack 1
• There is an intermediate certificates
  • on both the 2003 boxes (haven't checked the 2008), the intermediate certificate does appear the Certificate (Local Computer) -> Intermediate Certification Authorities\certificates in the Certificates MMC Snapin
  • openssl s_client -connect <server>:<port> -CAfile root.crt indicates the intermediate is installed properly
  • It appears to work fine on other devices; but I've only done limited testing
  • Under IE 7, Firefox 4/5 we receive no errors (tested under Windows 7)
  • Under Firefox 3.5 we receive no errors (tested under the newest Ubuntu)
  • Looking at the logs, I don't see any entries from the mobile units (although this is problematic as the server is really busy this time of year, so I could have missed them)
  • In double checking the supported cipher suites, the working 2003 server has been secured (it passes PCI scans), so its supports fewer cipher suites than the non-working server, so I don't think its a cipher suite issue.
  • Finally, I have tried to manually compare the certificates
  • CNAMES, serial numbers, etc are obviously different
  • On the two which work they have Object Identifier (2 5 4 9) = 154 W 12th Avenue where as the one which doesn't work has Object Identifier (2 5 4 9) = LEAVE_THIS_FIELD_BLANK (the reason is we have a centeral group which actually submits/approves them and the centeral group is supposed to replace that text with the correct street address. Obviously they missed it.)
  • If you think its a problem, I can fairly easily have the certificate re-issued; I just hate to do it unecessarily.
  • (Edit) Also, I've hooked up a laptop the same way the handhelds connect and can connect just fine; thus I don't think its a networking issue.

I would greatly appreciate any suggestions on how to proceede. I think at this point my options are:

1. Match the ciphers suites so they are identical (I doubt it will help, but the more apples to apples the better)
2. Ask for the certificate to be re-issued with a correct address
3. Move the webservices the hand helds use to communicate to one of the two servers they do work with (undersireable as they are open to the world where as the non-working server is only open to our WAN network; it could work short term)