If your clients use JCE for linking articles local to the site, they probably use something like this:
In this particular case the generated link (in the editor) is: index.php?option=com_content&view=article&id=3:seblod&catid=15:seblod-3-1-x&Itemid=122 which in the browser will translate to /categories/12-content-construction-kits-ccks/15-seblod-3-1-x/3-seblod (you know the drill), provided that Search Engine Friendly URLs and Use URL rewriting are turned ON.
As you can see, all relevant info (Category, Id, Itemid) are there. If on the other hand they (your clients) insert the url by hand, the previous answer apply - the navigation will be restored once a visitor browse to previos/next.
Both Seblod and Joomla! breadcrumbs are showing the correct path.
P.S. I am using Joomla! 3.1.5 and Seblod 3.1.5 for this test. I can give you a link and access to a test site, where you can see that by entering the link in JCE this way, the navigation is kept in check.
P.P.S. Maybe you could post your Seblod > Site (tab) configuration, which will help understand better why your navigation does not work properly.