How high does my fishing skill have to be to fish somewhere other than stormwind or dun morough (sp?)  ?  I'm a level 42 and just started to work on my fishing skill, so everywhere I go to try to fish says 'skill not high enough.'  Where else can I fish and at what skill level?

I don't know the exact fishing levels for different areas, but have you tried using lure? I would think you could go to Lakeshire and do the fishing quest there now, but you might have to get lure for you pole which is sold by fishing trainers/ vendors.  But if you never see the "fish got away" message anymore, then you can probably move to a higher level area.

i have found this guide and table to be extremely useful.

http://www.wowwiki.com/Fishing/Locations

good luck.