I was hoping someone else would jump in at that point and supply something useful. So here is more "thinking out loud" about this.
One of the goals of [storytelling or not] Alice is to provide an environment that motivates the learner to press on and solve problems. The interests of blind people are as wide and varied as anyone else, but you have an opportunity to tailor things to their interests because you have to do something unusual for them anyway. So find out what grabs them, what they'd be interested in getting the computer to do.
The next important thing about Alice is the avoidance of syntax errors. At present I see no way around that for blind users. So the next best thing is choosing a language with decent error messages. You want one that is sufficiently simple to parse that the line numbers are really where the problems are, and that the line numbers are reported. If you are working with speech or braille then you can't take in a whole screenful that easily, so Tcl's approach of almost no line numbers and quoted context will be a pain.
They may be proficient with a text editor already, or they may been pushed into using something like notepad (I believe the Braillenote comes with a version of windows built in), in which case teaching them something better (with searching, substitution, and indenting) would be doing them a favour. Even good old ed from unix, available in various forms for the PC, would be a tool worth knowing as it teaches regular expressions, and its command set is used in vi, sed, ex, and sort of made it into Perl.
What sort of applications? If you are on Windows with .NET 3 then speech is pretty easy to access, and will have a certain appeal. Text games would be of interest, I suspect. Text based interactive fiction (
http://www.xyzzynews.com/) may be of interest. Of course you might lose them in some Colossal Cave and never see them again, but it might inspire them to want to program something of that sort. That site has lots of systems for writing adventures which are pretty much programming, involving different classes of objects. I could never keep up with "shoot-em-up" games even as old as Elite on the BBC micro, so this would make sense.
If they are mathematically minded you might be able to use sound to explore numbers, like the chaotic bifurcation diagram. Or mathematical simulation, moon lander games. Or given an embosser for braille, how would you generate a text file to represent various shapes, bar graphs, etc? Or if you have access to a MIDI interface, computer generated music using a few simple rules might be explorable. Markov chains are always a favourite, and are reasonably easy to explain. You can apply that to music or text. Tree data structures and "think of an animal [, vegetable or mineral [or modern major genera]]" are possibly sufficiently interesting to explore: real machine learning in action. Years ago I got a book called "How to build your own Expert System"
http://www.amazon.com/Build-Your-Own...1599706&sr=1-1 which has a fiarly gentle intoroduction to the perceptron and discusses large neural nets without getting as far as explaining back propogation, IIRC. The programs in it are in BASIC and are well explained.
That's probably more suggestions than you ever wanted, so I'll shut up for now and hopefully someone else will see this thread and join in.