Digging for fossils can take a fair while. In Diamond/Pearl you could only get one of the fossils (i.e. cranidos in one game, shieldon in another). I believe in Platinum you can get both but one is really really rare.
I'd suggest you try and work more quickly. Note how many items are in the wall when it first comes up. If you start uncovering a sphere, give up in that area (unless you particularly want the spheres) and try somewhere else until you've found everything. This way you're more likely to find good items quicker.
Just keep trying and you'll get one eventually!