Ok, for starters I'm using 2.5, but I noticed that a lot of people...including myself was having the notorious previous/next entry link problem, and I discovered a fix that works for me. I can only hope that it might work for some of you as well because I understand how frustrating it is to have something broken.
On my index, my query is calling for a maximum of 5 posts which is great and all, but what I didn't notice before, that I just realized is that in my control panel --> settings --> reading...I had 'Blog pages show at most set to *10* posts. I changed this to 5 to match my query and everything works fine now. I can use previous/next entry links and I don't even have to touch my permalink structure.
If you're using the showposts bit, make sure it matches your settings.
I hope this works!