You are probably having trouble downloading the CRL file from their CRL Distribution Points. If you open the cert's properties - details tab - look for CRL Distribution Point field you should see some URLs that they publish to - see if you can open those in your browser or not. It should open a Save/Open dialog and maybe a security warning (since you know where its coming from, okay to save). Whether or not you get this dialog is a basic measure of success.
This should go over TCP port 80 in most cases as regular http web traffic. See if there are any restrictions in place, or maybe flush your proxy, clear your temp files/cache/history/etc. If affecting a whole site, I would suspect that site's proxy cache as serving up stale data.