Boolean Difference Tool Not Changing Shape
I don't have enough reputation to comment but looking at the blend file you posted, it looks like the normals on both objects are flipped inside out. Using "Make Normals Consistent" on both meshes seems to make it work okay.

You said you already did this, though. Perhaps the "Inside" checkbox is checked for you? I didn't see that in the blend file you posted though so I'm not really sure. But the skull mesh in your screenshots and both the meshes in the blend file you posted are definitely inside out, you can tell from the weird purple black thing they've got going on.