MySQL Replication Troubleshooting
Something tells me that when you run SHOW SLAVE STATUS\G you get

Slave_IO_Running=No
Slave_SQL_Running=Yes


It is a connectivity issue back to the master. This is a not connectivty due to the network but with the binary logging mechanism of the master. This is definitely the case because, the error message (1236) is complaining about the first entry of the master's list of binary logs.

When you had setup the line

[mysqld]
log-bin=mysql-bin


This would naturally create a file called mysql-bin.index, a files that would contain the list of all binary logs that starts with mysql-bin.

Just run this on the master:

SHOW BINARY LOGS;


and you will see the list of binary logs on the master. It shold look something like this:

+------------------+------------+
| mysql-bin.000001 | 1073741824 |
| mysql-bin.000002 | 1073741824 |
| mysql-bin.000003 | 1073741824 |
    .
    .
    .


There are a few scenarios that could have occurred:


Not every entry in the master's mysql-bin.index existing in the master's datadir
The master had a problem writing a binary log that the slave needs
One of the master's binary logs is either zero-length or corrupt


You may need to sync the data like this:


service mysql stop on the slave
Run RESET MASTER on the master to zap the master's binary logs
Perform rsync of data from master to slave multiple times until rsync &lt; 1 min
service mysql stop on the master
Perform final rsync of data from master to slave
Find the master's log file and its filesize
service mysql start on the master
service mysql start --skip-slave-start on the slave
On the slave, perform change master to using master_log_file='mysql-bin.000001',master_log_pos=filesize of master's log fiie
Perform START SLAVE; on the slave


Give it a Try !!!

I answered another question back on Feb 23, 2011 about creating a slave from a running master : MySQL Replication - Introduce new Slave to replication