First of all, you are jumping in on a 7 year old post......
Second, you should post in the Pontiac forum, under Grand Am's.....
So you replaced the starter/solenoid, cleaned terminals, and it still won't start....
First thing you should have done, was check voltage at the battery, with the key in the crank position(above 12 volts).....then check to see if you had the same volts at the other end of the battery cable on the starter.....if ok, then you check the purple wire to the solenoid at the "S" terminal.....should be 0 volts.....when the key is in the crank position, it should be battery voltage....If you have battery voltage when in the crank position, and all connections are tight and clean at the starter, and the negative cable to chassis ground from the battery is good, with no voltage drop, then bad starter(you won't be the first to get a bad one)...
However, if you don't have battery power at the purple wire at the "S" terminal, with key in the crank position, then you have to work your way backwards on the purple wire, through the Park/Neutral switch, then through the ignition switch, to the fuse......in fact, try starting the car in neutral with your foot on the brake...
But, if you have the PassLock system, which I think you do, maybe the PCM is not grounding the starter enable relay....Under the hood there is a fuse block....find the starter enable relay.....put your hand on it and have someone turn the key to the crank position......if you feel/hear the relay click, then try swapping the relay with another with the same number on it....
If it doesn't click, and the relay is ok, if could still be a P/N switch or ignition switch or fuse.......but more likely it's the PassLock security system......