TL;DR Be sure you've got trunking enabled on the switch!
It appears as though I solved my own problem! The switch ports were *not* configured as trunks as I had thought. When clearing the configuration of the interfaces, I had run the appropriate "switchport mode trunk" command but somehow, it didn't stick. As a result, none of the VLAN tagging was working. Hence the error message in my original post. Effectively, the "trunks" were configured as access ports on VLAN 1.