Submitted as a (rework design) bug but also posting because someone may have a hint.
Nat Pagle quests are simply brain check in Classic. You achieve 225 in fishing, you get the quest, you buy +75 lure, and you win - required level is 300.
Afterwards, you could even ignore them and return at max level for fun.
My character was converted from 346, result is Classic 300 and Outland 46. Also 1 in WLK and 1 in Cataclysm.
Kalimdor was fine. In Swamp of Sorrows I catch junk about 90% of the time.
I sort of doubt that it’s broken for 3+ years (since the profession rework) but it kind of is. What’s the bug?
Also, some kind soul, please go to Wowhead and add a comment. Last comment is several years old (8.x) and reports no issues.