I set up Signup for the first time, with CCK Date (6.x-2.4) enabled on my event node. As soon as cron ran I received my reminder email for the event. The node's date field was set for August 17 (a month from today), and the reminder was set for a day in advance. The email had the %node_start_time token, which came out correctly as August 17.
Everything else date related worked thus far, and i couldn't find any similar issues here. On a hunch, I dug through the code to find out where the date comparison was.
I found this was the value for $reminder_start in the _signup_date_reminder_sql function in date.inc:
DATE_SUB(STR_TO_DATE(field_date_value, '%Y-%m-%%dT%T'), INTERVAL s.reminder_days_before DAY)
The pattern in STR_TO_DATE had an extra % before the d, which was causing STR_TO_DATE to return NULL and mess up the date comparison. As a result, reminders were sent as soon as the function was called.
Being more of a designer then a developer, I just stuck a str_replace() in there to make the %% a % for a temporary fix (which works for now), but I dont have the developmental know-how to find the deeper cause of the problem. It might have something to do with the Date module, but I don't know.
One other thing: the date field I used only had year/month/day granularity, and therefor no timezone handling if that might be problematic.