This problem is purely with the host OS atm - the amd64 and i386 packages there - so I don't think I should be hitting up against Testing/Unstable issues. I looked further into the breakage and realised libmp3lame0:amd64 had an invalid version:
# aptitude versions libmp3lame0
p A 3.99.5+repack1-3 stable,testing,unstable 990
i A 1:3.99.5-0.0 100
The package must have been installed as part of the special install required for avidemux from the 3rd party Debian Multimedia site - once I force 'downgraded' it to the known version, avidemux needed to be removed.
Once I sorted that out, I was able to run pcsx normally after some SPU2X configuration
I would like to donate £20 to you - do you have a Paypal address? Thanks for all your help - running this in the host OS is definitely an improvement.
I'm very disappointed that even with OpenGL3.3, pcsx2 release build still fails to run GTA3 at normal framerate, and when smoke is on the screen, can easily get down to 25fps. In Final Fantasy X, Shiva's summon when she descends into the ice crystal slows down considerably too - I guess I'll need to wait another year or so to see if things have sped up enough to consider it a PlayStation 2 replacement (both pcsx2 and radeon improvements presumably).