tkMessageBox popup invisible when run from desktop, visible when run from boot
According to the tcl/tk documentation:
Setting the override-redirect flag for a window causes it to be ignored by the window manager; among other things, this means that the window will not be reparented from the root window into a decorative frame and the user will not be able to manipulate the window using the normal window manager mechanisms
So the window does not always behave has expected (it is less the case in Windows). For instance, in Linux, the window does not get keyboard focus (python tkinter overrideredirect; cannot receive keystrokes (Linux)).
If what you really care about is to have a fullscreen GUI, just replace
root.overrideredirect(1)
by
root.attributes('-fullscreen', True)
and the window will behave normally so the message box will appear on top of the main window.
Another possibility in Linux is to replace
root.overrideredirect(1)
by
root.attributes('-type', 'dock')
This tells the window manager to treat the window as a dock, and at least in XFCE, it results in a window with no decorations, always on top of the other windows, but the message box does appear on top of it.