How does your Library handle the 4k Erase sector size? do you use a triangle buffer? The Uno only has 2k of ram. If you need to change a value in the flash you have to erase an entire 4KB sector.
I wrote a similar Library, but I added a 64KB SPI Ram chip to use as a temporary buffer to copy the sector data into. My library first verifies that the write is possible (memory bits can be programed to '0' only), if a bit is already '0' and needs to be a '1', it copies the corresponding sector to the SPI RAM, initiates a Sector Erase, merges the new data into the SPI RAM image, then after the Sector Erase Completes writes all non '0xff' bytes back into the FLASH by 256byte pages.
Chuck.
check out my Kickstarter Memory Panes a 1MB RAM expansion Shield for MEGA2560 projects.