Yea...it sucks! If none of the patches work for you I'd reinstall 1.5 and hold out till they get a permalink update finalized.
I upgraded to last night's alpha build and my permalink problem went away I've probably broken something else in the process, but at least my archives are working properly now
Wow - my ability to put things off with no end in site has finally paid off... I guess I will chill with my WP 1.5 until WP 2.0 finally get sorted.