I have a similar problem to this: Replication has failed; how to get going on again?
Essentially my slave failed, and now complains "requested WAL segment 0000000100000135000000E4 has already been removed"
In my case I HAVE done a full base backup again as per the instructions http://wiki.postgresql.org/wiki/Binary_Replication_Tutorial#Binary_Replication_in_6_Steps. So I shut the master down, did a full rsync, started up the slave, then started the master. And I still get the same error.