I'm a long time user of Ubuntu, but I'm not a fan of Unity.

Here are my issues/needs:
1. I don't like Unity (it's just not for me, and where it puts the Window controls, file menu, etc. yeah so not for me)
2. I love the Software Center - it's just bar none to Synaptic. I dread having to use Synaptic to find new software.
3. I like to have the latest and greatest stable wise. - I do want to try a Debian Testing distro in a VBox and see how I like it.
4. I'm a Gnomey, or at least a customizable desktop that doesn't take a lot of work (Lubuntu 11.04 has issues with the panel at the bottom for system themes, same with Xubuntu 11.04, it's more confusing for trying to get it themed to where it looks decent now - usually messes up the libnotify theme)
5. Gnome 3 PPA just does not work on Ubuntu 11.04; it works then something breaks, yeah I can keep from updating it, but there are still some stability issues.
6. It has to be a FREE distro, no RedHat here.
7. Must be able to install gstreamer codecs, eclipse, games, virtualbox, etc.

Now here's what I'm thinking about doing:

Linux Mint 11 (to be relased this month) is going to be Gnome 2.32 still, not sure where Mint 12 is going, waiting to hear on that. So I'm planning on Installing 10, upgrading to 11, and continuing for a while if I can.

Here's what I've thought of and my reasons against:

Fedora 15 - Yeah, package installation isn't that great. SELinux is a pain! (Newb at SELinux) and it's just not for me. Otherwise I love it, very fast Virtualization.

OpenSuSE - Package installation is the same, Synaptic with a tiny different GUI changes. Also, causes my computer to overheat, I've found fixes (cleaned fans, changed system properties on OS, installed drivers, etc.), but still runs hotter than Ubuntu - about 10-15 deg. C hotter.

Kubuntu - Not a big KDE fan, and though I've got it to work, it doesn't feel like my computer I run into more issues with Kubuntu more than Windows ME (and that's saying something there).

PCLinuxOS - Uses Synaptic

Sabayon - Has very few packages and I believe it uses a source-based installation where it's based on Gentoo (I could be wrong).

Slackware - I'd have to compile most of my stuff, that's a pain, even with the SlackPackages that does it for me, I've ran into issues with Virtualization software.

----
Now I could be wrong and some of these things may be easily fixable or that. Is there a distro that has a moderate to large amount of packages, has a software type center installation method, uses pretty much the latest but is stable, would prefer DEB but can be RPM, and does have Gstreamer codecs without compiling?

Also, Ubuntu 10.04 LTS won't work either, I like anything with kernel 2.6.33+ 2.6.35 has tons of nice features in it.

Is there a specific distro for me?

You answered your own question, go for mint.

Kind regards

Debian with Gnome?.
You could either run Stable with the .38 kernel from Backports or use Testing.
Just my £0.02.

Linux Mint. Exactly what you are describing.

Sad thing is, now I'm liking Kubuntu (now that I got rid of the annoying notifications). It's weird, it's like with the annoyances of the notifications I feel like I have control over my computer again. I still have Mint burned and ready to go - guess next I need to do some performance specs.

It's all very personal, only you can decide what works best for you.
If you want control, go for Slackware.

Kind regards

Control is just an illusion one moment you have it other moment you are as good as dead.
Go for mint its really good.

1- Dont like unity? Then you probably want to get off the ubuntu horse now. 11.10 will still have gnome avaibke to install, but I wouldnt be at all suprised if they delete gnome 2.X for 12.04.

2- Software center should be installable for most, if not all the newer debian based distros. I know you can install it with debian no problem..not that I bother, I prefer synaptic.

3- "latest and greatest stable wise" is probably a bit of an oxymoron. Still, Debian testing is pretty stable, I've found it to be at least as stable as newer ubuntu versions.

4- I wouldnt base my opinion of Lxde or Xfce from the ubuntu variants. Apart from one Xfce theme (with odd requirements like "Murrine Engine (SVN version)") I've never had a problem appling themes to Xfce. BTW, gnome 2.X isnt going to last forever, unless somebody takes up maintaining it (like trinty for KDE 3.X), so its probably a good idea to have a better poke at Xfce.

5- Canonical isnt going to do much work at all to get gnome 3.X going with ubuntu, its comptition to unity in a lot of ways.

6- Most of them are free, depending on your definition. If you were thinking of going in the Red Hat route, there is CentOS.

7- Should be just as easy to install gstreamer, etc. with debian as it is with ubuntu/mint.

IMO, newer kernels do have some neat featuires, but if you dont need the features (like TRIM), its not that important.

+1.