Scrooge,
Did you install the latest newnews.pl I attached a few posts up?
Install that and if it still doesn't work, I'll see what I can do to help.
The newthread and new reply doesn't actually rely on templates for posting. It's only the quote that needs template changes... and that works.
The other two are simply extracted from the database when newnews.pl runs. It does this by checking a flag (isusenet) in the post and thread tables. This can be set -1, 0 or 1. 0 means it's a local post and will never be sent. -1 means it's already gone to usenet, and 1 means it's pending. Do a query on the post table and check if any are still set to 1.
The other point to remember is a reply to a post will only go to usenet if the post to which it is replying has a valid usenet message ID. If the parent post originated on the forum, it won't have this until we re-retrieve it from the news server on the next batch run. Replies will be held until that retrieval is made. This is why the useragent must remain static otherwise we can not identify which posts came from the forum.
Obviously, new threads do not suffer from this limitation as they do not have a parent.
Anyway... install the latest newnews.pl and report back