Quick lazy method I used... updated rom manager, deleted all the .nomedia files, rebooted with clean dalvik cache! Seems to have worked. ^^;
Anyway the solution posted above of only clearing data for the specific multimedia apps like gallery and music players seems 100% flawless.
This issue was more like a pain in the "S" than really a "problem"! I'm glad it's more than fixed.
Don't mind the sig it's outdated. Besides I'm testing JB roms and kernels, it's not practical to update this yet.
Phone: LG P500 (previously) - Nexus S I9023
ROM: NexusBeam 4.2.3
Kernel: 3.8.0-franco.Kernel-CRESPO-#1.2+francisco@francisco #12
Recovery: ClockworkMod v5.0.3... something, don't recall but it's the latest CWM Recovery :P