I can't seem to be able to delete them? what is going on?
With the Bitcoin.org client you can easily edit an address to clear the label.
But the ability to delete an address from a wallet is not a built-in part of the client. One reason is that some people give out an address and it is used multiple times for payments. If the address were deleted any future payments to that address would not show, and those funds could not be spent.
There is a utility, pywallet, that can be used to go in a forcefully remove an address.