Okay I seem to have automagically fixed the problem somehow? This morning it still wasn't working so I left the gamepads to charge and left for an hour to take care of some chores. Came back, still nothing, so I removed them (again) and re-paired them (again).
Been working ever since. Tried several reboots, a hard power off, they now re-pair upon pushing the PS button like magic. Maybe they just didn't have enough juice in them yesterday? I really don't know what else, I only left them for 5-10 mins on the charger to test things out. Either that or it was some freaky glitch.
The system and all the packages have been updated to their latest versions last night.
Anyway, I guess that settles it. At least for now. Hopefully it doesn't start acting up again.