I've noticed that CompUSA sales people seem to know nothing about Macs except about how to sell them. Whenever I ask a question, I get a dumb, useless answer.
Anyway, back to your question. ALL the G4s have Altivec. microsparc is right, the new G4s would be a waste of money if they didn't have the velocity engine.
BTW, you might want to wait until the January MacWorld Expo so APple can maybe release new revised G4s.
-Blakhawkg3