When Windows Update or Office Update fails, I employ the old fashioned method to download a patch on it's own and running the installer for said patch.
Here's the article with a link to download it.
I just installed Office 2003 Student/Teacher. I selected the Upgrade installation because I already have Office XP. Immediately after installing 2003 I checked to see if there were any Critical updates. There was one KB828041 which I tried to download and install. I'm getting an error message "Installation Unsuccessful" I've tried several times and keep getting the same message. Does anyone have any ideas?