What is your actual fishing skill? It sounds like the quest givers think that you don't have very much fishing skill, as fishers with under 60 or 80 skill points can only fish shallow water and gain in skill. (I forget the exact number). Have you tried logging out and back in again, that will often "fix" a lot of quirks it seems. Also double check your actual skill on your fisher and make sure you did put the skill back on if you have not already done so.
Try grabbing one or two more quests, to make sure it was not just the random luck of the draw. If none of these help, I would definatley report it as a bug. They have a HUGE bug reporting thread at top of UHall.