While trying to speed-up the site by turning on caching and some optimisations, I've ran into a problem with the Deco theme used on the site. Apparently, when CSS optimisation is turned on, it all gets messed-up (most notably the fonts don't look right). After checking out the <a href="http://drupal.org">Drupal</a> site, I've ran into two useful links, <a href="http://drupal.org/node/317059">http://drupal.org/node/317059</a>, and <a href="http://drupal.org/node/317059">http://drupal.org/node/317059</a>. So, basically I did what they suggested, turned on CSS optimisation, cleared the cache, and voila - it all works now.
Now, it may not be a huge improvement in speed, but at least now only two http requests are sent for the CSS files, instead of something like 6-7 before. For those who can't divide, that's 3-3.5 times less http requests getting sent at my server.
Update (2009-10-09 00:29):
Well, I <em>thought</em> I had solved it, but another issue appeared. This time it looks to be related with paths to images. I'll need to look into this some more.