From what I've learned, the Appbrain Market will NOT work on these devices, as they are tied to the regular Market...and as I posted elsewhere, these things will NEVER be capable of accessing the market as they are, unless someone figures out or codes some new ROMS for them.
Sorry for such a late post, but I have indeed found a working appbrain apk.
Then as I was going to download songbird from appbrain... It couldn't download. It said it didn't recognize the android market. Which makes sense, considering the Cruz doesn't have one.