Setting the AVRISP MKII clock to 125kHz worked!!! Thanks @Coding Badly, I wouldn't have solved that on my own 8)