I spent some time trying to figure this out, so I figured I might as well post it here.
Exchange likes to do things in the last possible second when it comes to creating mailboxes or free/busy data.
That's right, when you're finished creating a user and their mailbox, the mailbox isn't actually created, Exchange just knows that it has to create a mailbox for this user. When the user logs in via Outlook Web Access (OWA) or Outlook, the mailbox is created the first time they log in. On the other hand, if a user tries to log into Outlook Mobile Access (OMA) browse or synch, as the first operation on their mailbox, the command will fail. This is because OMA does not create your mailbox. Simply log in to OWA or Outlook and create your mailbox, then synch or browse via your mobile device.
Additionally, the same is true for free/busy data. If you've never used your calendar, others cannot view your free/busy data because the store for you has not been created yet. Once you create your first calendar request or appointment, it takes up to 15 minutes for Outlook to tell the server that you now have free/busy data, and for others to view it.
Of course if your double booked every day from 8am - 6pm, you won't have that problem.