Ok, so I got this phone last Saturday. Sunday, downloaded some odd number of themes, put them on the phone’s memory card, and installed 3 of them. Installation went fine, and the phone is currently sporting a non-Nokia theme.
So, Monday night (last night, dummy), I tried installing the other themes, but I got the “Expired certificate” error message. Thinking that it was a problem with the theme installers, I moved on. Checked the Nokia Download! app on the phone, and tried installing IM+. After downloading (weird, on first download, after reaching 93%, it went back to 0% and started downloading again), the phone displayed its “Preparing installation”, and after a few seconds, “Expired certificate” appeared.
Nokia is in for painful headaches. Look at this thread and see some problems being experienced by other owners of this phone. I wish Nokia luck.