SQL Server Log Shipping Randomly Stops Copying and Restoring
I spent a while in a test environment trying to reproduce your issue and have had some success.  If I set up Log Shipping in its most basic form, and in such a way as to mimic your situation, everything appears to be working.  However, I have found one way to configure the environment that results in messages similar to yours...

Message 1:


Message 2:


Let's walk through how I configured things in order to get the messages above:


Opened the Log Shipping properties on the Primary database.
Clicked "Backup Settings" and entered the same network folder for both input boxes (such as \\NetworkLocation_\DestinationForLogBackups).
Clicked "Ok".
Clicked the elipse (...) button to the right of my Secondary server instance.
Entered the destination network folder for copied files (such as \\NetworkLocation_\DestinationForLogCopies).
Checked the "Disable this job" checkbox down in the lower right.
Clicked "Ok"


The key to causing these errors is number 6 above.  This causes the following scenario to take place...


The Log Backup job backs up to a location (we'll call it "A").
The Copy job does nothing as it is disabled.
The Restore job attempts a restore from the location specified in the Copy job tab above (we'll call it "B").
The Restore job finds no suitable log files to apply in location B because they are all being backed up to location A and NOT being copied over to B (due to the Copy job being disabled).


The end result is not a clear error message outlining the root cause, but instead misleading messages that cause confusion about what is really happening.

This all seems to fit your situation, except for your comment:


  First of all my copy jobs are all working fine, it appears to be the
  restore jobs that are having a problem.


It would be a good idea to verify whether the Copy job is indeed enabled and is working as expected.  Look through the history of that job carefully and see if any of the information above helps you in identifying what your next step should be.