If you're finding the initial sync is taking a long time, you might wish to set up the app using a Wi-Fi connection (rather than your phone's mobile connection) to speed things up.

The length of time it will take depends on how many tasks and notes you have in your Remember The Milk account. If you have quite a large account (particularly one with many notes), it may take several minutes to sync initally.