Hmm. Sounds like you managed a small sequence break. As far as my research has shown, there's not much you can do. However, using Dig will allow you to get out of the ship. Try teaching via TM if you don't know it. If none of your Pokemon can learn it, consider turning off the game without saving to start over from your last save point. Obviously, you should search for a way out a bit more before trying that.
Tip: Put your DS in Sleep Mode and take a break. Sometimes all you need is some time for your head to clear, and suddenly the puzzle is easier. Trust me.