Replication has failed; how to get going on again?
Yes you will have to give the slave a new base backup (for streaming replication only steps 1 to 4) of the master. 

Your problem has probably occured because the value of wal_keep_segments is to low. The value needs to be high enough that when the slave is down for some time the master won't start recycling segments the slave hasn't processed yet.