How about an instant messaging client that can handle AIM, Gmail, Twitter, IRC, etc.... but with one key feature:
A custom protocol for Friend Codes that would piggyback various instant messaging protocols(ie: transmit via Gmail addresses, but result in a friend code/friendly name being displayed -- this would cut down on the need for a server).
The basis of this would be as follows:
+ User enters chat client information/logs in as they would normally.
+ User inputs all friend codes for every game owned(with a custom designation for each game).
+ Friend codes get submitted to a single database.
+ Users download said database, friend codes are parsed into saves.
+ When user decides to play a game, a notification is sent to everyone subscribed to the database, sent as an instant message, or tweeted to a Twitter channel.
+ Other users send a friend request, being fully aware that their request will be answered without having to negotiate a game via other means(phone, Wii message board).
* Optional features could include a save parsing system/thread watch system(via Ocarina or other) that would keep score and submit tallies to a database. Users could then look at others' scores, much like they can via Xbox Live.