iTunes 10.6.3 on OS X 10.5.8 works with the store (from U.K.). I can authorise, browse, deauthorise in the store.
Have you tried another browser? Firefox may be worth a try - I think it has it's own 'certificate store', so it may work if the system store is broken.
Is the Mac working for other secure sites?
Can you login to https:// Gmail, Amazon or any other httpS site you have a login for? If your certificates are damaged, invalid etc you may be unable to create a secure connection for other sites.
/Applications/Utilities/Keychain Access has a system for updating the certs in the Preferences > Certificates tab, enable OCSP…
On 10.5.8 I have 'best attempt' for OCSP & CRL. With OCSP as the 'priority'. I don't recall changing these so think they may be the default settings.
I don't know how to trigger updates for this system, reboot & see if anything changes! I think it may be triggered by visiting secure sites or it may just be a background job.
What versions of OS & iTunes do you have installed? iTunes 4 seems old - the store was introduced in that version. Check software update again 🙂