dont know how to fix it tho, but save your saves and reinstall teh game, takes 5-10 mins =)
How far down are you? It's possible that you're at Bedrock, which is indestructible. Or! Are you on a multiplayer server? If so, there's a few possibilities. If you're close to spawn, things can, will, and DO respawn as soon as you mine them. Or just lag.
Is it on multiplayer? and if so is it right by your spawnpoint that will bug it up
there are a few things that can be happening.
first one is if you are at the bottem of teh game ( al long way down). you will find "bet rock" you cannot destroy that. second thing it could be is that you are trying to mine obsidian or diamond or gold or red stand. those items require a strong pickaxe to remove. look it up. if you play online and you can't remove anything then ask the host to make you admin. the you should be able to remove blocks. if its non of the above send a message to notch with the problem.