En la función Introducir_empleado estás usando la variable "anterior" sin inicializarla, solo tienes que obtener el último de los empleados en la lista y asignarselo a "anterior" así:
Código:
...
...
Pnodo anterior, nuevo;
char c;
for(anterior=l; anterior; anterior=anterior->sig)
if(!anterior->sig) break;
do {
cout << "Introduce el nombre del nuevo empleado: ";
...
...