You don't indicate the packaging you are using. If you are removing and redeploying the package that the mbean's class is in, you will have to redeploy it for sure. I'm somewhat surprised however that the redeployment isn't automatic. If you showed your packaging and more info about the dependency it would be helpful.
What does the stack trace say? Are you using cvs head? (you should be for this kind of stuff)