Does this mean that it's new starter time?
Probably.
Will cleaning connections make any difference?
Doubtful.
Is it possible to replace just the solenoid which seems to be the problem?
I don't think so, I messed with one once (from the SDL) and it doesn't really seem to be a user-serviceable part. If you are after reliability, and a basic connection cleaning doesn't fix it (and _did_ look like it was a problem), you will be best-served just by ponying up for another starter. -- Jim