Hello,
Unfortunately, JoomSEF cannot be upgraded from 3.x to 4.x, you need to make a fresh install of JoomSEF on Joomla 1.6. However, you can get JoomSEF 4.x for reduced price using the following link:
www.artio.net/e-shop/joomsef/joomsef-4-upgrade
Joomla 1.6 uses some pretty different code from 1.5, so JoomSEF 4.x is also pretty different from 3.x (from the programmer's point of view) so there is a possibility that some features will work differently in newer versions. But you can always try the free version first before buying the paid one. You can also purchase our support time to have our assistance with the configuration setting.
JoomSEF 4 works also with Joomla 1.7.
Best regards,
ARTIO Support Team