They might be serving a bad chain of intermediate certificates. That results in confusing errors: If your browser knows the intermediate certificate (because it has seen it on another website), it will work, but if it hasn't seen it yet, you get an error.