Well, nevermind about trying to get the Sea Chests from fishing, just consider them as an extra bonus while fishing. They will appear sooner or later