I have the same problem on 0.7.5 auto bootstrapping a 3rd node onto an empty 2 node test cluster (the two nodes were manually added) and the it currently has an empty schema.  My log entries look similar to yours.  I took the new token it says its going to use from the log file added it to the yaml and turned off auto bootstrap and the node added fine.  I'm bringing up a 4th node now and will see if it has the same problem auto bootstrapping.

From: Sanjeev Kulkarni [sanjeev@locomatix.com]
Sent: Thursday, May 05, 2011 2:18 AM
To: user@cassandra.apache.org
Subject: New node not joining

Hey guys,
I'm running into what seems like a very basic problem.
I have a one node cassandra instance. Version 0.7.5. Freshly installed. Contains no data.
The cassandra.yaml is the same as the default one that is supplied, except for data/commitlog/saved_caches directories.
I also changed the addresses to point to a externally visible ip address.
The cassandra comes up nicely and is ready to accept thrift connections.
I do a nodetool and this is what I get.

10.242.217.124  Up     Normal  6.54 KB         100.00% 110022862993086789903543147927259579701

Which seems right to me.

Now I start another node. Almost identical configuration to the first one. Except the bootstrap is turned true and seeds appropriately set.
When I start the second, I notice that the second one contacts the first node to get the new token.
I see the following lines in the first machine(the seed machine).

INFO [GossipStage:1] 2011-05-05 07:00:20,427 Gossiper.java (line 628) Node /10.83.111.80 has restarted, 
now UP again
 INFO [HintedHandoff:1] 2011-05-05 07:00:55,162 HintedHandOffManager.java (line 304) Started hinted handoff for endpoint /10.83.111.80
 INFO [HintedHandoff:1] 2011-05-05 07:00:55,164 HintedHandOffManager.java (line 360) Finished hinted hand
off of 0 rows to endpoint /10.83.111.80

However when i do a node ring, I still get

10.242.217.124  Up     Normal  6.54 KB         100.00% 110022862993086789903543147927259579701

Even though the second node has come up. On the second machine the logs say

INFO [main] 2011-05-05 07:00:19,124 StorageService.java (line 504) Joining: getting load information
 INFO [main] 2011-05-05 07:00:19,124 StorageLoadBalancer.java (line 351) Sleeping 90000 ms to wait for load information...
 INFO [GossipStage:1] 2011-05-05 07:00:20,828 Gossiper.java (line 628) Node /10.242.217.124 has restarted, now UP again
 INFO [HintedHandoff:1] 2011-05-05 07:00:29,548 HintedHandOffManager.java (line 304) Started hinted handoff for endpoint /10.242.217.124
 INFO [HintedHandoff:1] 2011-05-05 07:00:29,550 HintedHandOffManager.java (line 360) Finished hinted handoff of 0 rows to endpoint /10.242.217.124
 INFO [main] 2011-05-05 07:01:49,137 StorageService.java (line 504) Joining: getting bootstrap token
 INFO [main] 2011-05-05 07:01:49,148 BootStrapper.java (line 148) New token will be 24952271262852174037699496069317526837 to assume load from /10.242.217.124
 INFO [main] 2011-05-05 07:01:49,150 Mx4jTool.java (line 72) Will not load MX4J, mx4j-tools.jar is not in the classpath
 INFO [main] 2011-05-05 07:01:49,259 CassandraDaemon.java (line 112) Binding thrift service to /10.83.111.80:9160
 INFO [main] 2011-05-05 07:01:49,262 CassandraDaemon.java (line 126) Using TFastFramedTransport with a max frame size of 15728640 bytes.
 INFO [Thread-5] 2011-05-05 07:01:49,266 CassandraDaemon.java (line 154) Listening for thrift clients...

This seems to indicate that the second node has joined the ring. And has gotten its key range. 
Am I missing anything?

Thanks!