I have a kwikset 910 z-wave . After I removed it and paired it again, it actually works like a charm. The only problem is that the status change takes about 6-8 seconds. I.e. if you click on the lock button, it locks it within 2 seconds, but send the notification that it is locked 6 seconds after that.
What I would suggest, is rather than go to the lock and remove it, go to add sensors on the main page on the LCD, and hit remove. Then press the button the lock. That should unpair it. To be sure, even after it says removed, repeat it one more time and it will say "Unknown Sensor removed".
Now you should be able to add it. I noticed that the lock is very sensitive to distance when pairing. Make sure the almond is within 3ft of the lock.