CPU upgrade will benefit framerates in some games (SSD won't) but you'd really want to switch over to a Core i5 if you're upgrading. If that CPU+mobo is out of your budget, SSD will be awesome for Windows performance, boot times, application/game load times.
FX8350 looks good on paper (I'm afraid I actually recommended one or two to people in your situation) but there have been quite a few complaints about stop-start performance. Flawlessly smooth, then a pause, repeat. Apparently it's something to do with SMT and resource contention (whatever that means). If Scott_D drops in on the thread, he can explain that stuff. Doesn't affect all games anyway (not sure which are OK and which aren't), but worth keeping in mind.
SSD!!! The 4100 is plenty of CPU for 90% of tasks out there. You probably won't see a huge upgrade in gaming with a new CPU either. With an SSD you'll notice EVERYTHING is faster, smoother more enjoyable. It'll make all other computers feel like slow turds. The CPU/RAM/GPU have all been upgraded, but you're still bottlenecking everything on a decade old design.
SSD All the way, anyone with one can vouch for how nice, fast and responsive their computer feels.
Upgrading to an SSD has been said to be the single most significant upgrade you can do. However, for running games, it will not affect your FPS in any way. All SSD's do decrease your read/write times. This improves your boot speed (quite significantly), and allows you to load games faster. If you like restarting your computer a lot it definitely helps. On the other hand, upgrading to a different CPU wouldn't do much for you in games like BF3. It is said that BF3 uses mainly your video card, but it is true in multiplayer that your CPU is a huge factor in your framerate. But, your CPU should work well enough for BF3, and any other game. I would go with an SSD if you don't want to spend the $$ on a new motherboard and CPU from intel, because let's face it, Intel is the best in the business at this point in time. AMD just may make a comeback, though, so keep your eyes out.
Get an SSD for the most overall performance. First person loading into a game feels awesome. You always get remarks like "NASA wants their computer back."