It seems to be a timer - once you start fishing in a particular spot, it starts a timer. After some time (having tracked it) it won't let you fish there for a while. Usually moving to a slightly different spot works, but I don't know how long the reset on the timer is, so it could be possible to time out on all the fishing spots in an area.
And yes, I'm fairly sure it is a timer because I have started fishing, fished once and realized my inventory was full, had to run back to town, come back to fish 30 minutes later and I get the same message.