I have promotion codes set to be used only once per user. I have tested them by entering the code on checkout1 and then updating the totals. I don't actually check out and pay. The next time I try to use the code I get an error saying the code is not valid. But I haven't actually used it. Interestingly, the error doesn't occur when i'm logged into the CP in another tab in the browser. I tested this because it happened with a buyer who loaded up her shopping cart and used the code, but then was called away from her desk. When she came back, she refreshed her page and got the error. She can no longer use the code, even though she hasn't used it to check out.
This probably isn't because the promo code has been used - it's because the user is logged out. If you have the "per user limit" set on promo codes, then users must be logged in to use them.
It's possible that the customer who walked away from their desk was logged out in the meantime, which would explain why the promo code no longer worked.
Can you test this by making sure that you are logged in before adding the promo code to your cart?