compaqdrew, The reason I believe it's related to your network card is in part the information that I found on the forum that I posted above and from my experience
with my own Computer. Just before I posted above I did some testing with my pc and found that when I unplugged my USB wireless network card and tried to use time machine it gave me the error that we are all trying to fix. In turn I reconnected the usb wireless card and connected to my network and everything worked again, I also tried leaving the usb wireless card plugged in but not connected to any networks and tried the program an it worked. So this leads me to believe that
it has some sort of dependancy on a working network card, or it could be that it just doesn't like a wired network card. Do you have the ability to try a wireless network card? FYI all real mac's (non hackentoshes) have both a wired connection and a wireless connection so maybe it's dependent on the wireless card more so than a network card.

My Specs.:
OS: MacOSX Leopard 10.5.2 by Zephyroth
Processor: AMD Athlon™ 64 4000+ / MMX, 3DNow!, SSE, SSE2, SSE3, x86-64
Motherboard: MSi K8N-Neo3 Platinum (MS-7025)
Graphics: NVidia GeForce FX 5200 - working out of the box
Hard Drive: Seagate (160 GB) IDE
Sound card: Realtek ALC850 Audio - patched and working
Memory: 1 GB
Fast Ethernet by Marvell 88E1111 PHY -(not working - disabled in bios)
Fast Ethernet by Realtek 8110S (1000Mbps) - (working out of the box but not used)
USB wireless network card (Hawking Technologies for mac) - working with vendor drivers