Comment GAMBAS : free (GPL) Visual Basic-like for Linux (Score 1) 709
It is very similar to Visual Basic with a nice IDE, but it is free (as in beer and as in freedom, under the GPL license), and works with Linux (it is included in major distributions).
http://gambas.sourceforge.net/en/main.html
You can easily make GUI applications (GTK, Qt) with the visual form designer (so it is motivating) while learning basic programming constructs (if then, while and for loops, ...) Later, you can use to teach more elaborate stuff like connections to databases (MySQL, PostgreSQL).