Alright I have fixed it... Thanks to those who replied.
What I had to do is enter a new name in the "Root Tool Name" field which I had empty, but I had others empty too and they worked, then when I saved it BAM in the toolbar.
In my company we use a shared network filesystem to store all the macros so all users have access to the same macros. After an upgrade, I changed a macro in a higher version of Alteryx than what the end-users were using. This caused the macro to disappear for them.
Adding "Root Tool Name" made it re-appear for them.
But... if they drag the tool on to the canvas they get the standard error "This workflow was created in a more recent version...". That of course is an obvious fix.
Just letting everyone know, if you have an issue like "The macro was there yesterday and is gone today", it is probably b/c someone else saved it in a higher version.