Hola.
Si tuvieras un backup, si. :-/
Si no, me temo que es complicado. Existe alguna herramienta para sistemas de ficheros ext2 pero son demasiados archivos.
¿accidental?
como root...
rm -rf /usr/bin
Bueno supongo que de alguna manera podrás ejecutar dpkg-scanpackages ( o como sea) y obtener un listado de lo que tienes instalado y luego forzar la reinstalación.
S2.