First I would re-synch the SUS server to ensure that it is up to date, verifying that there were no synch errors. Then, locate the SP4 approved entry in the Approve Updates window. Click on the "details" link which should bring up a dialog box that shows 4 entries. All this just to ensure that the SUS server is up to snuff.
Now, at the client, I would ensure that the configuration of the WU is all correct. Make sure it is pointing to the correct SUS server, etc. It would seem more likely that the problem in somewhere in your client config as it should be relying on the server to tell it what it needs.
Another thing to mention is what is the state of the PC when it is scheduled to pull from SUS? Is it logged in or at the C-A-D screen? SUS reacts differently depending on who is logged in when it is set to go off.
Feel free to post a complete days worth of log file from a client (altering any private info) for review. Relevant server side logging would be helpful too.
Let us know.
Mr E