Our current setup is autobackuping plugins/worlds every 12 hours, whilst restarting the server every 24 hours. (Though we do not use AutoSaveWorld for the auto-restarts)

I checked my backups folder, and see this: (/backups/plugins)
http://hastebin.com/renebomiza.rb
This is showing that it's only backing up every 24 hours? Is this because of restarting the server before autosaveworld can get that 2nd 12 hour backup in?

'Backup' config section if needed:
http://hastebin.com/laquxopamo.sm

Is this a new "bug"? Or is this just plugin functionality?
(I swear it used to backup every 12 hours seamlessly)

Yep, timer is reset after every restart. In previous version it was saving, but due to rewrite it was lost. I'm currently reworking threads and intervals so they all are preserved after restart, but this may take time.
You should schedule to backup at specific time using AutoConsoleCOmmand instead.

Okay, thanks.

Unfortunately this won't be added, because intervals and such will be removed in AutoSaveWorld 5.0. The system will be changed to use settings and a separate scheduler for tasks.