I have had the same thing happen with my Linkstation and my MacBook running 10.6.x.
Yes, it does have to do with the application firewall supplied with the MacOS and it does happen even though the firewall has been set to accept incoming connections from NasNavigator2.
I saw something in a KnowledgeBase article at Apple one time, just looked it up again and here is the link
For an application to be able to be automatically allowed by the firewall to accept incoming connections it needs to be digitally signed by a Certificate Authority trusted by the system. For unsigned applications the MacOS puts up the dialog we have seen, and if you choose 'Allow' the MacOS will digitally sign the application and add it to the 'allow' list.
Here is the point that applies to the NasNavigator2 software:
"Some applications check their own integrity when they are run without using code signing. If the Application Firewall recognizes such an application it will not sign it, but then it will re-present the dialog every time the application is run. This may be avoided by upgrading to a version of the application which is signed by its developer."
So it looks like what we need is a version of the NasNavigator2 software that is digitally signed by the developer using a Certificate Authority trusted by the system.
The only other way to prevent the dialog from appearing every time you boot up would be to turn off your firewall. Maybe you don't want to do that though. I don't want to, myself. It is quite aggravating to have to respond to the dialog every time though.