I just came back and tried fishing on my old character again. I was in Port Jeuno for maybe 45 minutes trying to catch Black Sole. I managed to catch 10 Sole while fishing for just 45 minutes before I just could not catch anything anymore (ie. Fatigued).
I got .1 skill up in that time, making it feel very nearly impossible to ever get fishing to 100. (or cooking too for that matter since that is why I was fishing for materials).