You sir, are a genius! Did as you suggested (other than sign out and reboot) and it updated straight away.That's a drag!! I've had the same issue before when setting up iMessage on a new Mac. It seems like it always resolves by itself after awhile. Try turning off "Enable Messages in iCloud" and turn it on again. Other than that, sign out and sign in again, and try restarting the machine.
For me, sometimes after just sitting there forever, it says at the bottom left "Downloading Messages from iCloud." And then I just wait.