Hey there. The first line's rule should not ever match the next line's because the + after [^/] indicates
1 or
more (not 0 or more like * indicates) characters that aren't of class forwardslash.
The ? after the final forwardslash indicates
0 or
1 characters (i.e. final forwardslash optional).
So the first one will only match things like Cat1/Story_Name or Cat1/Story_Name/ and the second one will only match Cat1 or Cat1/ and the URI terminating there. Things like Cat1// will not match either rule due to not having one or more non-forwardslash characters between the two forwardslashes (first rule) or not terminating after one forwardslash or the category name alone (second rule). Gnome sane?
Unless there's something I overlooked, I don't know why swapping them fixed your problem. I'm thinking there must be something else strange on the go there, possibly a non regex-related bug.
Edit: As an afterthought, if you have Category names with any characters that Pligg URL encodes (turns into something like %28) than make sure you change them back to the actual characters for the rewrites (you may need to escape them), because the rewrites look at the
decoded characters. So if you have something like InternetRadio%28Streaming%29 then change it to InternetRadio\(Streaming\) for the rewrite