OK, this could be one of two things:
a) wireless reconciliation not in line
b) permissions not right on your notes PAB
As far as B goes, do you know the name of your Domino BlackBerry server? If you DO, please open your Address Book in notes, and click on FILE > DATABASE > ACCESS CONTROL LIST, and let me know what level of access the BlackBerry server has.
If you do not know the name of your Domino BlackBerry server, you need to talk to your BES Admin.
As far as a) goes, try this: Blackberry not sync'ing address book with BES