I was able to resolve this by editing the VB script used to remove the print queue, which included legacy printers.
The script is written as such:
On Error Resume Next
Set ObjNetwork = CreateObject("Wscript.Network")
objNetwork.RemovePrinterConnection "\printserver*printername*"
There were 39 objects listed to remove that were legacy, so the time out before the script would skip to the next was causing the delay. Once I removed all the old references, the rest of the process ran in about 90 seconds from start to finish.
The reason the legacy entries were there was because we recently migrated to a different print server and needed a way to make sure that all users were up to date with the new print queues.