I would prefer a recipe to build the toolchain myself from source, but if you happen to know of a site with binaries for the SB1 under Linux, I wouldn't be horribly opposed.
For the latter I'd try broadcom, they've been pretty good about shipping tools that are known to work on the board. That said, for building from source I'd try Dan Kegel's crosstool script. That's what most people use.
If you're still having problems let me know - perhaps it's something obvious.
-eric
