Fraudulent *.google.com certificate issued

Did you check if Firefox had cached the intermediate certificates? It can make things appear to work, but when you try with another computer which has not visited yet any site which uses the same intermediate certificate, it will fail.

(I believe Firefox switched to also caching intermediate certificates because, since Internet Explorer caches intermediate certificates, a lot of people forgot to put the whole chain on their servers, and it "worked" on IE but failed - as it should - on Firefox.)