Hello,
well, it might be due to upgrade to 1.5.9.
Certainly make sure to keep your version of JoomSEF upgraded - it is FREE. Just go to JoomSEF Control Panel, click Upgrade and then click Upgrade from ARTIO server.
The newest version will be downloaded and installed automatically.
Also, if you are using JoomFish at your site, make sure to apply the patch. JoomFish has been lately causing generation of lot of invalid URLs.
If you still keep having problems with URLs, please, post some examples here. (always post SEO and original non-SEF URL). Thanks.