Why did you change the battery? Like Mike asked....did this problem start before or after the battery change? If you had the problem before the change it could be you just have a bad starter. If it was after the battery change either the battery is no good or you have a connection problem somewhere.