Very strange seeing that the typical HC chip has an input load
of several MEGA Ohms (ie no current used) the LS has an input load
of several Kilo Ohms (input current <<1ma) and any AVR can sink or
source up to 20ma!! A stupid question I know but are you sure ALL
your ground pins on the chip are going to 0V? Have you measured it?
Yeah, I smell a rat too. It's just NOT this hard to drive common logic gates.