Sometimes the upgrade date can be moved up if you pay a lot per month because of a larger plan, unlimited sms/data, etc. You pay off your subsidization quicker.
Yes-- i pay $250/mo on my plan (international data & etc) and also bought the iPhone4 subsidized day 1, and my message says I am eligible for an upgrade now.