I remember reading somewhere that upon arrival in Hispaniola, Columbus found beaches that were so plentiful with lobsters that they appeared red. It is possible I read this in a book by Bill Bryson, either "at home" or "a short history of nearly everything". Does this sound right? Does anyone have an actual reference?
Adding to what @Alex said "typical" lobsters (i.e., the lobsters that humans eat and the ones that turn red when you cook them) don't even extend as far south as Hispaniola. They are a cold-water species and based on available range data for H. americanus don't even extend southward of North Carolina.
There are crustaceans referred to as "lobsters" in the Caribbean region, and they are red, so your reference might have been talking about them, but they aren't true lobsters, they belong to a different group of crustaceans (Palinuridae, the "spiny lobsters", versus the true lobsters in Nephropidae.
I very strongly doubt that, growing up in the Caribbean. The type of lobsters found there are neither red nor at all capable of getting out of the water.
At most you'll seem skim-walk on sandy bottoms, as they don't really swim either. You'd have to be coming onto a beach in which lots of them congregated in shallow enough water to be seen from topside and appear to cover the sand. And even then, they wouldn't be on the beach.
Land crabs? Maybe.
Those lobsters do migrate in groups, so an occasional sighting of a big group, underwater, is possible.
I'll chalk this up to the kind of strict adherence to facts that resulted in maps adorned with dragons and mermaids.