Another possibility is that even a new chain may have a stiff link that will make it skip. Try putting the bike up and watching the chain go over the cogs as you spin the pedals. You may be able to see one link that doesn't bend as well. The best way to loosen it up is to put some lube on it and rock the link back and forth (across the way it is supposed to bend, not with it's normal bend). This may seem like you're going to break the chain, but you won't, and it works.