After spending the past 6 weeks searching the web for a fix to this problem I finally found one that actually works!
https://barefootdevelopment.blogspot.com/2007/11/fix-for-wordpress-paging-problem.html
The code he created was to fix an issue with WP 2.2.1, but works perfectly in 2.6! Hopefully this will be helpful for the rest of you guys.
