I have scoured the forum and the documentation looking for the solution to this problem:

In my c:\Program Files\nusphere\templates directory the following files DO exist:

New Style.css
HTML File.html
Include File.inc
Javascript File.js
Php File.php
Php5 File.php5
Perl File.pl
Python File.py
SQL File.sql
Text File.txt
Xml File.xml

However, the only files that show up in the "New File" chooser, are:

HTML File.html
Include File.inc
Javascript File.js
New Style.css
Perl File.pl
Php File.php
Php 5 File.php5
Python File.py
SQL File.sql

Where is:
Text File.txt
Xml File.xml

Or any other templates I add into the /templates directory ... Should they NOT automatically be included and added to this listing?

What is the deal?

New File would show only registered file types, the files with extensions listed in Tools->Settings->File Associations.
If, for example you associate XML with HTML parser, you'll see it in the list too.
It makes sense because the IDE needs to regognize the file type and assign appropriate syntax highlighter for it.

Those filetypes are registered though:

yeah, got it...
seems, that's a bug then.

Was this bug ever fixed? I am evaluating 4.5.0 and I am not able to create a txt file

Yes and no.
If you need a txt file, just add this extension to the list of extensions for say html files (they all are texts, right?), then create "Text file.txt" in phped\templates
and this file will be shown in File->New dialog.