Comment 9 for bug 287719

I can confirm this problem is still persistent with scim on karmic (9.10). However I found a "workaround" on the interrnets: http://forum.soft32.com/linux2/Nautilus-find-type-ftopict57901.html

You have to use scim-immodule instead of scim and it works. To switch use: im-switch -c
This however is not a completely satisfying solution as there seem to be problems with scim-immodule and it's use is not recommended (or so I've read), though I've had no problems so far.