There are places that you can get custom bottles of champange - I am not sure how good the champagne is -- but it's the bottle that makes it special - -
You could get a custom label - and have all your names on it...
Makes it a really special gift...
http://www.signaturewines.com/
(Their champagne is a Mumm's Sparkinling wine and it's not that bad -)