One technique i used to use years ago for trouble shooting terminal services but can be applied here, generalizing Stu's tip.
Do not use a default Service account but one you control eg:NettalkSVSaccount, that you access
On your server, login with these credentials, and "emulate" what the Service is doing by going straight to the CMD prompt and simply try to Launch your NTserver as normal app, eg YourNTApp,exe, after you hit enter, thats pretty close to the state it would be if launched as a service.
remember your service can have no user interaction. (if your adminstrator runs something to tweak the users environment on login, you might want to check that, as, typically that's not applied to the service. Things affecting user profile, home directory, printers, shares etc)
so if it is not working then pay attention to everything you do to make it work, because this what it it needs as a service, you will learn for next time:)
( this is where you might see, that you are running from the wrong folder, missing a permission, PATH does not have something critical, or perhaps you prompt for something that as a service, it cannot respond to, firewall issues etc), You have to make it so the app can simply launch.
d) Now set the service to use these credentials and try again.
you can then apply other policies to the service account if you want. or with the knowledge you have gained, you may now know how to
deploy for any other servers or service accounts.
HTH
poul