Is there a switch located on the shift linkage on the transmission (should have 2 or 3 connectors attached to it, like a 4 pin and an 8 pin or something)? The listings I have show the switch used on 2000 and 2001 Impalas, I'm not sure what they use for a 'Manual lever position switch' on the newer models. Are you sure it's not a 2002?
Other issues to look at are the starter and associated wiring. Is the security light on when it won't crank?