I have also noticed this thing.. not sure what is going on.. I assume.. they might be trying to target ads by geography (as in adwords advertiser has this option)... and for sometimes they are unable to catch the location or whatever..
But I am sure Google is also aware of this problem.. and looking into it :)
I think that the problem may be to do with picking up context/keywords on a new page, as I had this message yesterday when I loaded up a new weblog. The new material would have been presented 'cold' to AdSense, so it had no idea what ads to place. By the time I refreshed the page it was working fine.