Can you show a screenshot of the actual message, or at least the complete wording of it?
Is it possible you are actually seeing the message that your Update Service itself has an update, rather than WDP? There have been a number of recent posts from users who have encountered the problem of the Update Service requiring an update but then failing to complete. I'm not sure what the final solution to this problem is.