We encountered a crash with the tool when run in background (certain circumstances made it happen), as such we didnt feel comfortable releasing the product with the issue. We were unable to narrow down the cause in the time frame we had to fix it, thus the only safe option we had was to make the tool foreground only. We're actively working to fix it for the next service pack.
I'm not in a situation where I can test 10.0 easily, but I can tell you it was found at 10.1. Its possible it exists in 10, but my understanding of the issue: I think its a 10.1 issue only. (was specific to having table windows OPEN while removing the join).
Add Join got just as much focused testing during the analysis of Remove Join and it worked fine as far as I remember.
Are you running Add Join in a model, or just as a tool stand alone?
If you're using it as a model, you need to make sure all data input (layers) are exposed as parameters. If they arent exposed, the data isnt sent to background. And of course, if the data isnt set, background cant work on it.
This help topic, specifically Issue 1 explains this in more detail.