Yeah was going to say FAT32. I always thought there was some kind of limit with this as well.
However, I have an external 250GB hard drive, that works on both my Mac and my Windows laptop.
For me there was no problem. It was simply a matter of formatting it on my Windows machine, and it just worked on my Mac! So it works no problem on both.
I must say though, I have two other 500GB external drives that I have formatted for the Mac, in the Journaled format, and the speed difference is remarkably increased, especially when searching - to that of the drive that works on both. Perhaps this is a very obvious statement to make but however
Hope you get sorted.