please post all your information (schematics, code, test results) otherway there is little help we can provide...
i think... maybe you are forgetting or messing with the i2c packet. most examples use small i2c memories (24c01 to 24c16) which only uses 3 bytes to write a random position (i2c_addr , mem_adr, mem_dat) all enclosed in (i2c_start and i2c_stop) and the three having an acknowledge... after issuing a simple i2c memory write, you must wait something like 10ms to get the data written... don't read the data before! (mostly the memory will report NAK until it finnished the process)
on higher capacity memories (like your 24c512) you need a 4 byte i2c packet (i2c_addr, mem_addrH, mem_addrL, mem_dat) so if you issue a 3 byte packet you will get all acknowledges(up to set address) but not making and actual 'write' (no data sended)...
the same to read a random position... the address setting follows the same logic (2 byte on first example and 3 bytes on last example)...