I lost my address book icon today as well. I've already searched by checking for the Hidden Icons.
I lost the icon after having installed WorldMateLive (WML) via the Blackberry website. I then uninstalled/removed the WML hoping that the address book icon would reappear. Unfortunately it did not come back. The address book itself is still on my BB, I just do not have the icon.