Just FYI, I am running the filemaker server 5.5 on Windows 2003 Server R2 64-bit.
How are your users attempting to connect to the shared database? Open Remote?
Do they get anything to open or do they see this message immediately before they can even get the file to open on their machine?
FMP 6 and older files are notorious for requiring multiple files in order to function as a relational database. Any chance there's another file out there you didn't find and get moved over to the right location on the new server? Any chance that one of the files is marked single user?
Also, what networking protocol have you set up your network for? (FMP 5.5 supported some older network protocols in addition to TCP/IP).
If TCP/IP, any chance your new server has a different IP address from the original? You might have a file reference that refers to a file by an IP address that no longer exists.