There are plenty of online complaints about people being unable to install S60 themes onto their E65. Doesn’t help that Nokia included the butt ugly Dots and the boring Nokia default theme and nothing else on the phone.
Well, here’s the solution I found online!
Goto Tools -> Application manager > Options > Settings.
Change Software installation from Signed Only to All and Online certificate check to Off.
Enjoy. Download my Nokia S60 themes from here. They’ll work for E-series and N-series phones, but not the E61 or E61i as I’m too lazy to modify them for landscape screens.