What does your cassette look like? The chain and the cassette usually wear as one unit and oftentimes are replaced at the same time. It's possible that the cassette has worn to the point where it doesn't match up well with a new chain now.