You have adequate permissions, right?

Yes, I have full control. We created the site and subsequent Project
Task List using the Application Template: IT Team Workspace. In our test
environment, we still have the New button, but not in Production. FYI,
we started from scratch in the Production environment.

Are you using any authentication other than Windows Aunthentication, for
example forms based authentication? The New button disappearing is often a
symptom of Client Integration being turned off, which usually happens
because some form of pluggable authentication has been implemented.
Pluggable authentication (forms based authentication) has client integration
turned off by default.

No, just using Windows Authentication. Did find out some other news,
which puzzles me... The site admin checked 'YES' to the list settings of
'allow multiple content types'; when I changed back to the default of
'NO', the button reappeared. This should not affect the ability to see
the New button on the Project Task list toolbar, should it?

Maybe if you haven't specified any content types, it doesn't know what you'd
want create so it doesn't offer the option?

If the "New Folder" option was also removed, that might make sense.

That's probably the problem. By default it shouldn't cause an issue, but
one of the things that happens behind the scenes when you enable 'allow
multiple content types' is that it changes where it looks to find the
templates that are used by the New button. When you only have one content
type the template is stored in the Forms directory under the list or
library. When you add additional content types the templates are stored in
a subdirectory for each content type. If the system doesn't find a
template, then there is nothing to show on the New button. If there is
nothing to show on the new button then the New button won't show. You
shouldn't turn on 'allow multiple content types' unless you are going to add
an additional content type at that point.