Okay, I did some looking around and figured it out.
The issue was with the qtconfig - since I don't have KDE/etc installed - it was using the default QT interface. I am using ArchLinux (+Xfce4) so that might be why as well.
On the command line: qtconfig
Dialog pops up, select, e.g. "Cleanlooks" as the GUI and then select File-> Save (or CTRL+S) and then File-> Exit (don't 'X' the window- for some reason that wasn't saving the config for me).
Restart Opera and :-o it's pretty.
Edit:
I found this link just after I solved it myself- this might help others who are experiencing the same issues.
http://my.opera.com/Pedric/blog/2007...-qt4-interface