Windows 7: Internet Connection Sharing - Enable

I have a laptop that has connection via a WiFi connection. I also have a desktop that can't use a wireless card. I also have a wired router nearby. I'm trying to share my laptop's wireless connection with the desktop via a wired connection. So, let's call them WiFi and Wired. I've tried several things from my laptop with no success:
1. Standard Cat5 connected to the WAN in.
2. Standard Cat5 connected to LAN out.
3. Crossover to WAN in.
4. Crossover to LAN out.
5. Connecting the laptop directly to the PC using the crossover cable.
6. Checking "Share this connection" on the WiFi connection
7. Checking "Share this connection" on the Wired connection (this disconnected my laptop from the network entirely, so that's not it. I just needed to try everything).

The Wired connection is showing "Unidentified" and "Public network." I can't seem to change that. I seem to think that's where the problem lies. I've shared this connection before, so I know it's possible.

What do I have wrong?

EDIT: By the way, the desktop is running Ubuntu Lucid Lynx.