I had a look in the Berkeley DB and see that you are storing full paths to every file.
This means that if a file is renamed on the local Linux server, rather than via the AFP server, we will lose the CNID mapping and therefore also lose any shortcuts that pointed to that ID on the Mac side.
Why not change the BDB database to this format?
devID, inode, CNID
0, 1232, 324
That means that the file can be moved absolutely anywhere (within the same device) and still be found in the database, no matter what it is named.
If you are actually already doing dev+inode mappings, then please update your Netatalk documentation, because it doesn't describe this anywhere.
Consider queriying the Netatalk developer list, possibly someone cares to answer. Alternatively look for someone who provides consulting services.