Rebooting one of the switches in our redundant network setup resulted in resolving all network issues. After the switch came back online network issues started to manifest again. For now we've manually shutdown the ports on that particular switch to restore full connectivity. It seems like the switch thought that the port was up while it wasn't fully working. We are still investigating the root cause of this issue.