Solution Found
After a little Googling, I installed a Cydia App called "Poof". Alternatively, if you have "BossPrefs" installed, you can use it. Basically, open either app and cycle the "Turn off to Hide switch" for Categories from On to Off to On. This should then give you the icon. I also did a reboot.
New Issue - It seems that whenever you use Categories to change app icons or add/delete app icons, Categories disappears again, after the re-spring. Using Poof and recycling the On-Off-On switching bring Categories back.
Very strange all this.
Hope this helps 😛