yes it is most likely a connection problem...
as was suggested check the connections at the battery cables at the battery and the starter, clean them.

Also check the start voltage at the starter ignition wire on the solenoid of the starter and make sure you are not getting a large voltage drop, it should be battery voltage when the key is turned to the start position.

Also check the neutral safety switch on the transmission and it's connections. If there are any voltage drops across this circuit replace the switch.

NEVER file on the starter bendix, if the teeth are showing signs of wear it should always be replaced.
Even though the starter may work 'off of the engine' there still may be a problem inside the solenoid housing, contacts are inside the solenoid housing, you can pull off the cover on the end of the solenoid (3 screws) and check the contacts inside it, if they are melted or burned badly you may be getting a connection but a weak one which would work under 'no load' but not connect enough to carry a load which would explain why it is not engaging the starter motor correctly.
If you find bad contacts inside the solenoid housing do not try to file them, once they are worn or burned you do not have much choice but to get it rebuilt, or trade it in on a reman.