Strange as this sounds, I have a 1989 Toyota Camry as my commuter and I had the same problem.

When I turned the key to start, all the lights would dim but I wouldn't even get a click from the solenoid.

I replaced the starter and the problem disappeared. Login to read more.