Haha some tough going here, but here are my best 2 album guesses:
In Media Res - Of What Was - from Vancouver I think, slow, folksy
The Minders - It's a Bright Guilty World - Elephant 6 band, def has horns, obscure, from Portland
No way it's Les Claypool (far too weird) but his first two albums were both in the Of 'X' and 'X' format. The Microphones fit your bill, but stopped playing as The Microphones and became Mount Eerie around 03 or 04, plus I guess they had some good success. When I read the "of x and x" I thought of "The Decline of Country and Western Civilization" by Lambchop, which is folksy, but I think they're from Nashville, and no horns and "The House of Apples and Eyeballs" by BMSR and Octopus Project, but the music doesn't fit and they aren't from the West coast either.
Sorry!
My last hope is extinguished. Not any of those.
I made a post on 4chan's /mu/ page, but it isn't showing up for me. Then again, I also just might be an idiot who doesn't understand how to use the site properly. Does anyone else see the post?