I have the same problem. When I try the exact same action in Firefox 3.0b5 it works flawlessly.
Bah. I had altered the handling of the $single variable for my template, and I broke Exhibit in the process. . . .Problem solved, though.
The reason it doesn’t work is because the function relies on the deprecated $post->$post_category call. The post_category name has been dumped in favor of that table (I forget the name) that allows multiple categories per post. Therefore, the next_post and previous_post functions are totally broken in 1.2 with regards to categories. I’m workin on a fix, but I suck at PHP so……