You don't have to get the longtooth hide from the island upon which Skull Castle rests - you can get it anywhere in the Enchanted Sea area and Talrik will be perfectly happy.
I was attacked by longtooth not far from Talrik infact, so you might want to head back there and look around. Otherwise, just keep exploring and they'll turn up.
Wyv
|