The crystal skull is loot from one of the skeletons in a cave in Broken Valley, a little south of the fortune teller (should have someone call out approaching the mining camp, and when you talk to the lone survivor he describes what happened in the mine before dying). I'm not sure if you can still get it or not after the battle tower, due to the poison.
