The 391 queries now showing is with the cache on, correct? Cause if I start refreshing the page, once in a while I get over 1100 queries, then it drops back to 400. Cache certainly helps, but it doesn't fix the problem.
If you look at Nick's statistics at the SEO mod page, you'll see that with the nic_bck's code it optimized on 50%, but with my code it's 80% optimized. But I'd first suggest disable that mod at all and see if any performance gained (all you need to do is replace code from step 2 with the original code from 4images package)....perhaps it's not that mod that causes such slowdown...anyway, 1156 database queries is way too much.