Go to Seaside Cave (where the Roggenrolas were blocking you before), explore, then go to the Crustle. Use the Colress Machine and you will fight it. Afterwards go outside and the Frigate will be there for you.
Also to anyone who might yell at me for spoilers, this is a topic about what to do in the game. If you didn't want spoilers you shouldn't have entered the topic