To Tradergem's point, did the pump come with a pulley, or did you put the pulley on?
If the pulley came with the pump, then send it back. (Most I have seen do not.)
If you pulled it off the old pump, and put it on the new pump, likely you bent it putting it on or pulling it off. Eitherway you will need to replace it. I would see if you can get one from the same vendor as the vacuum pump, they will sell ones that fit their shaft likely better. If not I do know last I checked O'Rielleys could still order a pully. Then to Tradergem's point buy a pulley removal/install kit this time to prevent damaging it when you press it on the shaft. (Your local auto parts store may lend or rent one, just make sure the threads on it are good.)
Keep in mind its the same thing with a Powersteering pump. On my 2007 F150 I actually ordered the pump and a new pulley ($15) so I did not have to goof around with pulling the old pulley and worry about it breaking or bending while getting it off. I just had to put the new one on with a pulley kit. Saved time and potential frustration. (See below.)
Post some pics and let us know how it ends up.