If you are starting to build an user-space for your operating system, you should discontinue using the i586-elf target but rather build a new and unique target for your operating system as detailed in
http://wiki.osdev.org/OS_Specific_Toolchain - the current revision of the article even mentions how to do so using newlib. Perhaps the issue is caused by not having adapted newlib properly for your operating system.
Truthfully, you should really learn newlib internals and its build system so you are able to resolve issues such as this yourself. I realize the autoconf mess of a build system it ships with is probably really hard to understand, but it does get better with training (at least in the cases where I've had to patch such packages for my OS).
Btw. --prefix=/foo is the location where the program/library will end up on your operating system at runtime, _not_ where it should be installed on your local machine. If you continue this practice, you may experience programs that inexplicitly tries to access /home/peterbjornx/nk/usergcc on your operating system at runtime. The correct solution when cross-compiling is to set --prefix= to the runtime prefix (the empty string if installed into the root directory) and then set DESTDIR=/home/peterbjornx/nk/usergcc when running make install. This might not be applicable in your particular situation, if you are installing newlib into the gcc cross-compiler prefix, but that is kinda the wrong approach, you should install it into your operating system root instead. (Feel free to disregard this advise for now if it works, but keep it in mind when you try to port more software in the future.)