I'm not sure if this is guaranteed to work, but I think it should.
Try going to the island and starting any tour with a few exceptions. Grab a fishing rod from Lloyd and go fishing in the rivers and for goodness sake, if you do catch one, make sure to put it in the basket before leaving the island! It's a little more finicky than just fishing in a town but it shouldn't be too bad.