Just a guess, since I don't have that app... first, what OS version do you have loaded on your device???
Early OS versions required you to remove all spaces and special charaters: ()-+, etc and you needed the entire number like in the US a number like 1 (888) 555-1212 should be listed like 18885551212
This was just to get the Contact list to display correctly on their device... so this Might be you problem, but we need more info.
i had this prob. you have to go to your address book and make sure hes deleted. then hit the blackberry button for menu, scroll to SIM phone book, click, and make sure hes gone from there too!!