Say I have a creature with the Soulbound ability, Stonewright, which is currently bound to my Llanowar Elves. If I play a Birds of Paradise, can I switch my Stonewright to be bound to the Birds instead?
Says right in the reminder text:
Of course, you can "reset" the soulbound by causing the card to cease to exist for an instant and re-enter the battlefield with, say, a cloudshift.
Another opportunity for pairing with another creature is of course if you lose control of the elves, if only temporarily; or if it leaves the battlefield.
These restrictions are made more explicit in the comprehensive rules where there is a lot more room to write out the two triggered abilities in full:
I was going to answer yes because the reminder text is a little bit misleading, as it doesn't actually say that both creatures have to be unpaired, only the one that just entered the battlefield. At a prerelease I've been playing, the local judge also said that you can break an existing pair when a new creature enters the battlefield, but the Comprehensive Rules say it clearly:
Side note: They even managed to bork up that sentence ("and this one and both are unpaired")