Error "Invalid promotion codes" thrown by iStore, yet promotion is consumed

In our test iStore, when applying a promotion code to the shopping cart, I frequently get the error, 'Invalid promotion codes" followed by the promo code I had entered.

In most of these cases, I don't understand why the promotion code is invalid.  But regardless, the store doesn't allow that promo to be applied to the order.

The problem is that even though the system thinks the promo code is invalid, it has still consumed it ("used it up").  Most of our promo codes are promotions the customer can only use once, so when EBS doesn't apply the promo to the order/cart, but does consume it, the customer cannot use it again.  I've documented this behavior in 2 different development/test instances.