You have to wait until after the Shimmering Island is destroyed.

Once that's done, take your chocobo out into the sea. Open your map and make sure your location dot is covering the dot of the shimmering island exactly. One you're there, use a dead pepper and he'll dig up Ultima Weapon.