Locke is in the Pheonix Cave. The Pheonix Cave is a mass of mountains that looks like a star with a small piece of grassland in the center to place your airship.

Terra is not in her house, and it appears that Katarin ran off as Duane was a bit angry. Go to the house on the left side of Mobliz and watch the dog carefully. Follow that dog downstairs and you will see Terra, Katarin is about to have a baby and Duane comes in and apologizes. He hasn't been the best husband but he is learning and wants Katarin to come back with him. Then suddenly the whole place shakes as Phunbaba returns. Then you must fight him.

You must go through Owzers house and kill Chadarnook to aquire Relm.

Take Relm to see Strago at the Fanatics Tower to recruit him.

And if you saved Shadow in the WOB you'll find him in the cave on the Veldt.

On top of the Fanatics Tower is a GemBox and a mini boss. The secret to killing the mini boss is casting life3 at the begining on batlle.