E-Newsletter Claims all users have already received a brand new Newsletter.

I am creating a new E-Newsletter. I created it, chose save and send. I send to everyone and I unchecked the box that says:
Don't send to people who've already received this:
============
Yet each time I try to send it still says:
All members have already received it!

I tried sending a test and that worked just fine. So I know the email settings are correct.

Any help would be appreciated.

Kind Regards,
Aoirthoir