Look at the website Coaly posted, and shop the game around a bit. Post a site locked/protected copy on the net and send some emails to different portals asking if they'd like to bid on it. Don't be afraid to ask for more money, if a portal gives you a hard time about it they aren't reliable; when you're dealing with money, it's always best to be businesslike and try to get yourself the best deal. Your game sounds like it's pretty big, so you could get a very decent amount for it. I've had games sponsored from $500 - $5000; it's really about how much traffic it'll bring in for the sponsor. If it's going to be popular and spread to a lot of sites, then it's worth more.
The deal you described in the OP sounds legit, though. Most sponsorship involves adding the sponsor's branding and a few links into the game. It's important to keep the copyright on the game so you can make sequels and reuse code.