Thanks for the reply. I will try recompiling newlib and then the firmware and see where that gets me. I assume that would require me to rebuild the arm toolchain from source?
Well, I found out it is rather easy to recompile the whole Yagarto toolchain, because it comes with very handy build scripts, so it is necessary just to modify the one used to build newlib (07-build-newlib.sh). It should be possible to just compile newlib, but you'd need to ensure all the options are correct, so there are binaries built for proper platform, with correct prefix so linker can find them etc.
Althought there might be one way to accommodate bigger firmware in the flash: by rearranging the flash memory layout and removing unused features, if there are any. I am not sure how many features you could remove to free enough space and leave the firmware to be usable, or enough flash blocks in application deployment area that can be moved to code region, but maybe if you are lucky, it can be done.
And, a bonus idea: if you don't mind updating the firmware via Atmel SAM-BA, you can compile version without the bootloader, which will free a few flash blocks at the beginning (14 blocks of 'bootstrap' type).