I believe so. When I uninstalled MSN Messenger, it did not fix the problem, as there were still registry entries for msmsgs. So I did a search and removed them and it fixed the problem. So did you have either of the messenger services installed?
BTW, I don't think the SP will have anything to do with it, as I have all updates for my Office software installed and encounter no problems.