Rebalance failed after power failure

We recently survived a major power failure on two of our four nodes. We only have one replica so I guess we just lost some information but this is not cruical.

The main problem is that now we can not rebalance ... After both servers returned I re-added them to the cluster. Now I see all 4 servers in my admin console - two with status "up" (green) and two "pend" (yellow) together with warning: "Fail Over Warning: Rebalance required, some data is not currently replicated!"

When I click "rebalance" it waits for a couple of seconds and then I receive error:

Rebalance failed. See logs for detailed reason. You can try rebalance again.

I tried many times but everytime I get the same error. And my logs say:

Event: Starting rebalance, KeepNodes = ['ns_1@192.168.0.3','ns_1@192.168.0.7','ns_1@192.168.0.8','ns_1@192.168.0.14'], EjectNodes = []
Module Code: ns_orchestrator004
Server Node: ns_1@192.168.0.7
Time: 21:51:40 - Wed Apr 11, 2012
 
Event: Rebalance exited with reason {wait_for_memcached_failed,"users",['ns_1@192.168.0.3','ns_1@192.168.0.14']}
Module Code: ns_orchestrator002
Server Node: ns_1@192.168.0.7
Time: 21:51:52 - Wed Apr 11, 2012

... and that's it..
I tried restarting couchbase but nothing seems to help. Any clues?

Thanx! Regards.