What I would try to do is:
1. download the newest JoomSEF 2.2.5 and trying to upgrade from file
2. making sure that all extensions are up-to-date as well
3. clearing all caches (JoomSEF & Joomla!)
4. if the problem lasts after this, the problem might be that the data are from 1.x while you are using 2.x and the upgrade did not work...
5. in such case, go and edit file administrator/com_sef/sef.xml and change the version number from 2.2.5 to 1.4.3 (or whathever you had installed previously)
6. then, repeat the JoomSEF update from file process (this should try to fix your DB as well)
7. if this fails as well, then your last chance would be to uninstall (delete) JoomSEF and install it from scratch or trying to debug the error and fix it manually