Paste what rules you have setup for it.

cat /etc/udev/rules.d/99-steam-controller 
# This rule is needed for basic functionality of the controller in Steam and keyboard/mouse emulation
SUBSYSTEM=="usb", ATTRS{idVendor}=="28de", MODE="0666"

# This rule is necessary for gamepad emulation; make sure you replace 'pgriffais' with a group that the user that runs Steam belongs to
KERNEL=="uinput", MODE="0660", GROUP="niqnutn", OPTIONS+="static_node=uinput"

# Valve HID devices over USB hidraw
KERNEL=="hidraw*", ATTRS{idVendor}=="28de", MODE="0666"

# Valve HID devices over bluetooth hidraw
KERNEL=="hidraw*", KERNELS=="*28DE:*", MODE="0666"

# DualShock 4 over USB hidraw
KERNEL=="hidraw*", ATTRS{idVendor}=="054c", ATTRS{idProduct}=="05c4", MODE="0666"

# DualShock 4 wireless adapter over USB hidraw
KERNEL=="hidraw*", ATTRS{idVendor}=="054c", ATTRS{idProduct}=="0ba0", MODE="0666"

# DualShock 4 Slim over USB hidraw
KERNEL=="hidraw*", ATTRS{idVendor}=="054c", ATTRS{idProduct}=="09cc", MODE="0666"

# DualShock 4 over bluetooth hidraw
KERNEL=="hidraw*", KERNELS=="*054C:05C4*", MODE="0666"

# DualShock 4 Slim over bluetooth hidraw
KERNEL=="hidraw*", KERNELS=="*054C:09CC*", MODE="0666"

Well, for one thing the suggested file by Valve is:
/lib/udev/rules.d/99-steam-controller-perms.rules
Try that and see if it works then, you may need to reboot for it to properly take effect.

My controller is alive again.

I changed the udev rules name (/etc/udev/rules.d/99-steam-controller.rules) but I'm not sure it's related.
Even with this name, the controller didn't respond at first.
I tried with usb/wireless, steam big picture/window mode, switching on/off the controller and try pairing in controller settings and it finally works.
I really don't know what makes the difference.

Hmmm, I seem to be having this same issue on Ubuntu 16.10... seemed like the 99-steam-controller rules were gone in /lib/udev... saw somewhere to install steam-devices... which I did, which also seemed to replace the rules but still no dice.

Will try rebooting and "adding" from within Steam a few times and hope I get lucky too.

If I'm not wrong, I don't have any rule and the controller worked fine until the latest update. I'm on the stable release on 14.04. Any idea? Is the rule mandatory? If so, why is not automatically created?