2
I had this problem in the past also. I think it had something to do with PHP. As I recall, I had problems with PHP5 but not 4. Also I ended up using XHLD and I gave up on the packaged one for whatever reason. At any rate, I'm using 2.0.13.2, PHP4, and XHLD. This is working well for me.
XHLD is more configurable that the standard headlines module. I know it isn't the only one. Try others, too. I was never satisfied with the original headlines module and come to think of it I don't think I ever got it to work.
Good luck.