I checked the example but it wasn't useful. And yes the pull up resistors are present - the other i2c devices work correctly on the same 'bus'.
I tried using the EEPROM.h library instead and that did seem to work fine so I think I'm going to just use that instead of AT24C256.h
It's weird though because I'm sure I had a sketch working with that library previously