I wish I could give you more specific help but there's one statement you made that caught my attention:
"The network sharing is working fine and all client PC's can access the network share folders files on the server. Similarly, users can browse to the database file and attempt to open it from there, but this returns a different error message."
As you've discovered, sharing a folder does not have any effect on how filemaker accesses a database hosted on another computer--whether by Filemaker Server or Filemaker Pro. Furthermore, the files should NOT be placed in a folder where sharing is enabled. Attempting to access such files directly from another machine can be hazardous to your data security and file integrity.
Are your users launching filemaker pro and then using open remote to attempt to see the database files? Can they at least connect to the sample database file?
Which version of Filemaker Server are you using?
Things to check:
Open each of the files with a copy of Filemaker Pro and check their settings under File | Sharing | Filemaker Network... Make sure Network Sharing is on and that access is permitted for all users.
As Filemaker tech suggested, check your firewall settings, as a quick test, turn off the firewall and see if things change. If turning off the firewall makes everything work for you, look up the firewall setting in your documentation and make sure that all the correct ports are enabled as your filemaker server documentation specifies.