Nothing is wrong with what you are doing. I've had to ask RIM Support to regenerate my keys a few times in the past 12 months because, on their side, something happens to them. I don't know exactly what (could be a timeout on them where you need to use them within 30 days or they die, could be someone tried to hack them so they killed all the keys from everyone and regenerated for those that requested it, etc.), but it happens. Usually they will get them to me by the end of the current business day, if I ask in the morning. Otherwise, the next business day they come in.