Wow, talk about running me in circles!

For replication to happen, you need consistent access to the replication log files. Those files should be there after a restart. Turns out, by default, the build of MySQL in Ubuntu 7.10 places these files under /var/run/

Every reboot, the files in /var/run were deleted. Boom, there went my replication. I just had to manually reconfigure MySQL to store these somewhere else and resync my servers. What a pain! After the fix, now my replication state continues after a reboot.

To fix, add the following line in your my.cnf under [mysqld]:

relay-log = '/var/replication/mysql-relay'

And, create a directory owned by mysql:mysql called /var/replication

Or put it somewhere else, that's just what I used. Make sure you do this BEFORE you set up replication, or else you'll hate yourself trying to move it later.