New Exchange Server 2007 mailbox stamped as legacy mailbox

If you use the Exchange Server 2003/2000 extensions to Active Directory Users & Computers (ADUC) console to create mailboxes residing on Exchange Server 2007 servers, these mailboxes get stamped as legacy mailboxes.
Exchange Server 2007 mailboxes should be created using the Exchange (2007) console or shell.
To remove the legacy tag from mailboxes created using ADUC, use the following command:

Set-Mailbox "John Doe" -ApplyMandatoryProperties

This is documented in KB 931747: A mailbox that is located on an Exchange Server 2007 server may be identified as a legacy mailbox in Exchange Server 2007.
To get a list of legacy mailboxes:

Get-Mailbox | where {$_.RecipientTypeDetails -eq "legacymailbox"}

Note, not all legacy mailboxes reside on Exchange Server 2007 servers, so it's not a good idea to use the ApplyMandatoryProperties command to all of these. Mailboxes residing on Exchange Server 2003/2000 servers are also legacy mailboxes, and you may see some mailboxes moved from Exchange Server 2003/2000 servers carry this tag as well.
Let's filter the above list of legacy mailboxes to only the ones located on Exchange 2007 servers:

Get-ExchangeServer | Where {$_.IsExchange2007OrLater} | Get-Mailbox | where {$_.RecipientTypeDetails -eq "legacymailbox"}

Apply mandatory properties:

Get-ExchangeServer | Where {$_.IsExchange2007OrLater} | Get-Mailbox | where {$_.RecipientTypeDetails -eq "legacymailbox"} | Set-Mailbox -ApplyMandatoryProperties