The issue that I was seeing was that after installing Virtual Server 2005 R2, I had subsequently added a NIC to the system. The host OS had correctly detected the NIC, and I installed the latest drivers. The problem was that the Virtual Server 2005 R2 interface was not displaying the new NIC in the interface. Just to confirm that I wasn't missing something, I tried adding a new virtual network (click Virtual Networks>Add>Network Adapter on Physical Computer), but when I went to select my physical adapter, only one adapter was being displayed.
After that I searched around and found that Mark was having similar symptoms, albeit not in an identical situation. Since the virtual machine that I needed to have running was needed for a beta test immediately, I didn’t want to uninstall/reinstall Virtual Server 2005, so I decided to look around a bit more in the interface.
Noticing the network adapter "Internal" (Virtual Networks>Configuration>Internal), I took a look at its configuration. This internal adapter had no physical NIC selected, but when I used the drop down window I found that the new NIC I had recently added was being displayed as an option. After that it was just a matter of changing the physical network adapter from none, to the new one, and re-adding a new "internal" adapter. After doing that, I then changed my Network Configuration section from the Virtual Server Interface on the virtual machine that needed to use this connection (while the virtual machine was offline). Finally, when I turned the virtual machine back on, it detected my new physical NIC, and I was then able to configure it.