A little bit late but we encountered the same problem.
I tried to restart the "Team Foundation Backgroud Job Agent", without any effect.
But I found a solution, although I am not sure if it is a bug or not.
We are using the Scrum Template for this project, and I have not checked this with any regular Project Template but I quess it is the same. First add the desired new iteration by right clicking on the TFS project and selecting the "Team Project Settings" -> "Areas and Iterations...".
On the Iteration Tab, we have now 2 iterations (at least in our case) with multiple sprints within these iterations. You can add a sample Iteration if you have only one Iteration
After moving the new Iteration downwards, so its new position is beneath the existing Iteration, I was able to see and select the new Iteration in my Team Query. If the new Iteration is already beneath another Iteration, simply move up the new Iteration
This may be a bug, or the use of the Scrum template might interfere with any sync process but the above method worked for us.