Run a trace in between the full backup and log backups. Capture things and look for any backup or truncate messages.

Something must be breaking the chain if this is not working.

If you manually run a log backup when this happens, what is the result?