Well poop. Now I'm back to this again.
E: Unable to locate package fs-uae
EDIT: OK, this is strange. If I open a ternminal, type in su, then my pass world, then type in "apt-get install fs-uae:i386", then it will download and install. Oddly enough there doesn't seem to be any improvement in speed, the direcotories still display somewhat slow. I'll install Picasso and see if that changes anything.
That was a typo on my behalf sorry. As you wrote, it should be fs-uae:i386
You should definitely install p96 as it will speed up a lot.
If you are still getting problems after that, PM me and I'll send you a working config and OS3.9 installation if you want.
Also it could be that you haven't got hardware accelerated 3D drivers installed as FS-UAE uses OpenGL for everything.