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.
