I tend to only have this happen on new installs of XP, which due to software requirements, still have to get installed from time to time. It doesn't seem to matter whether I launch AU from the Start Menu or from within IE, or if I click the "Express" or "Custom" update options.
Sometimes, you can force it from the command line:
These days I find Internet Explorer needs to be updated first.
(Or just google "Download Internet Explorer".)
I uncheck the prompt to install updates as I prefer to have control over what it installs.
Once it's installed, you can either wait or use the above command line to check for updates. There won't be many at first, but it does seem to get the ball rolling.