Buenas,
Fijate en concreto en esta ventana.
http://i.stack.imgur.com/AINnj.png
Tienes marcado la opción de "Allocate Console"?
Cuando has creado el proyecto lo has creado como proyecto "Java Project" verdad? No "Web Project", "DDMS project" o algo por el estilo...
Un saludo