Vuelvo a colocar el codigo completo jQuery con una modificación en cuanto al evento. Esta vez en lugar de usar keypress utilicé keyup.
Código:
$(document).ready(function() {
$('#nombre,#apellidos').on('keyup',function(){
$(this).val()!='' ? $("#mensaje").show() : $("#mensaje").hide();
})
})
Acá el ejemplo funcionando:
http://jsfiddle.net/4RPv3/1/
Saludos!