Nothing jumps out as obviously wrong with the way you have it all set up.
I would remove the criteria for "when status is Open" since you already have the other setting to only trigger at ticket creation and that should be all that's needed there.
Also, i don't believe that the tags will work in the subject of the email (but those tags will work in the "template" section of the email).
You might try making those changes and see if it has any effect. Otherwise you may need to open a support ticket.
Hmm, no dice. I had originally tried without the Status requirement anyway, that was just something I added to test. I removed that and took all the variables out of the subject and moved them into the template with no luck, guess it's back to Support...
We had a issue when we sent this up also. Check your email server logs/span filters to make sure the email you are sending from in the sending from in the help desk is a trusted email address.