I'm playing a game on 3.25 where I've just discovered Shipyards, and two of my coastal cities can't build shipyards (or ships). These cities are definitely on the coast (one has clams in the city radius, and both have already built harbors, lighthouses, etc.). In fact, one of the cities is my capital, and has the Colossus and the Great Lighthouse.
I have about a dozen saved games going right back to 4000BC (currently 1088AD). Neither city has ever been able to build ships (except for work boats).
The only odd thing I've noticed which might be causing the problem is that the affected cities are on fairly small seas instead of the world ocean. However, I've placed other cities in such a way as to provide routes for ships to get out of the seas and into the ocean.