Por que mudou
The classic naming scheme for network interfaces applied by the kernel is to simply assign names beginning with "eth0", "eth1", ... to all interfaces as they are probed by the drivers. As the driver probing is generally not predictable for modern technology this means that as soon as multiple network interfaces are available the assignment of the names "eth0", "eth1" and so on is generally not fixed anymore and it might very well happen that "eth0" on one boot ends up being "eth1" on the next. This can have serious security implications, for example in firewall rules which are coded for certain naming schemes, and which are hence very sensitive to unpredictable changing names.
Quando mudou
Depende da distribuição que você está usando. Começou com systemd
v197. Portanto, qualquer distro que estiver usando essa versão ou superior provavelmente usará essa convenção de nomenclatura.
O que as letras e os números significam
Não consigo encontrar nada para verificar isso, mas acredito que o p
represente o periférico physical e o s
significa slot. O en
significa e ther n et. Isso é exatamente o que eu juntei do link acima, mas isso não é explicitamente. Nem encontrei nada no Google.