As I understand it, Amazon selects certain devices to notify about the update, sending it out in waves. So I am not terribly surprised this will (it seems) not queue you immediately.
On the other hand, downloading the update manually (via your computer OR a jailbroken Kindle with a shell prompt running an invocation of wget) is guaranteed to get you the update immediately.
