I agree with what Michelle, Chris, and Alireza wrote. "I recommended (that) he call her" is correct but the first sentence "I recommended him..." is not correct.
Also, I hope I don't offend anyone, :) but the English in the response below that starts with "Well, first sentence..." has some errors in it. For instance, the phrases should be: "the first sentence," "If he were the subject," "then you could say it that way," "as the subject," and "then it would be correct to use..." Sorry, but I am just pointing that out so that any English language learners who read that particular response are not further confused. :)