A fuzzy is still far too small. You want a rodent that is as big around as your snake is at its widest point. A hopper is what I would go with.
just a heads up, pet store employees generally know very little about reptiles and tend to give out bad information about them.
You should wait at least 4 days in-between feedings, no more than 7 days.
Do not handle your snake at all until he starts eating for you.
What are your cage temperatures/humidity?
What are you using to provide heat?
What are you using to measure temperatures/humidity?