Here's a list of possible projects for those who are trying to learn C++.  These are great for building up your own style, snippets, and experience.  Some of the ideas here are drawn from a forum topic at http://www.daniweb.com/forums/thread32007.html

Coding is definitely the best way to learn C++ (and SDL).  If you keep at it, you might find yourself with a neat little program to share with friends or even to sell.  If you want to share any results with me, just send the source code in an email (sending executables is not a good idea).  If so, I might even open a section of submitted programs.

The great rule of good programming:
"Design or resign."
That is, you had better spend a lot of time (and paper) on the design of a project/game before you dive in and start programming.  Big projects can get overwhelming quickly.  Make sure that your ideas are possible and that you have the knowledge to implement them.  Did you sit in school wondering when web diagrams would come in handy?  Web diagram, your time is now.

If you need some introduction to C++, check out my C++ Tutorial.
And you can check out my example source files:
C++ Example        SDL Example
If you need help, just ask!

For a complete start on a polygonal platform game (similar to, but not tile-based like Mario), look here.

Updated 2/23/11
(I'll put new ones at the top for your ease)

Title	SDL	Beginner's Difficulty	Beginner's Time	Description
Memory	Y/N	*	**	Memory is a very simple and classic game. When a new version of a memory game comes out, the changes are always in the graphics, which points to the simplicity of the game itself. You can find these card games for kids with just about any Disney character on them. However, there is a lot of room for creativity. Take a Memory game and add something unique or allow customization.
Simple game	N	*	*	Part of my C++ tutorial includes my quick attempts at simple games.  These kinds of games include things like 'Guess what number I'm thinking of' and Tic-Tac-Toe.  This is probably the best starting point for a true beginner.
Steganography	Y	*****	**	Make a program that hides a text message within an image file.  This was my first project in an intro CS class, and I thought it was pretty cool.  The most basic form is to encode each bit of the text as the least significant bit of a pixel's red value.  Another program which reads this image would then look these up and stop reading when it came to a few bytes of zeroes.  If that doesn't make sense to you, send me an email!  There are tons of other ways to do it, too.  You can use my SPriG library to do all this with SDL.
Simple game	N	*	*	Part of my C++ tutorial includes my quick attempts at simple games.  These kinds of games include things like 'Guess what number I'm thinking of' and Tic-Tac-Toe.  This is probably the best starting point for a true beginner.
List Alphabetizer	N	**	**	I tried this one early in my programming life but couldn't quite get it.  At the time, I decided that MS Excel would do the same thing...  But the fire still burned...  I came back to it a few months later and finished it.  The main idea is to take a list from a text file (most conveniently as a command line argument), sort the list, then overwrite the file.  I found it best to work with the standard string class and file streams.  This project really dives into stuff that becomes very useful later on.
Hangman (themed)	Y/N	***	****	I played a PC Hangman game once, called 'Le Pendu' (kinda standard, I guess).  Obviously, it was in French, but that made it more fun to me.  I tagged this as 'themed' to invite you to make a Hangman game that is based on a particular idea.  Maybe the wild west or space.  Maybe Physics terms (Oh! My favorite!) or a different language.  Maybe even a scramble or another game mixed in.  To make this project robust, it should read from a text file.  Output would be nice using SDL (themes make more sense then), but it can be done very effectively using the command terminal.
Battleship (themed/changed)	Y/N	****	*****	Try making your own Battleship game.  You can design a theme or change some gameplay aspects to make it really unique.  This project should take a while to finish.  I have a friend who was assigned this project in an intro CS class.  It isn't really difficult, but it makes you have to be sure of your arrays and everything.  I did find this page that might help a little (if the link is ever broken, let me know).
Image viewer	Y	**	**	Use SDL and SDL_image to view images!  It's not very tough if you know some SDL.
Image editor	Y	***	****	This project can become something good really fast, but never seems finished.  You can use SDL and SPriG.  I would suggest having an idea of at least one neat feature that you'd like to create.  I personally would like to see an image editor with a better focus on editing alpha (opacity) values.
Snippets library	N	*	***	Write a utility library that provides useful functions each with a commented title, description, and keywords to use for easy searching.  Better yet, if you only include functions that are related, other people would be more likely to use it.
Sound player	Y	**	*	I was getting annoyed by Media Player having to load and popup on me every time I wanted to hear a short sound clip, so I wrote a simple sound player.  Mine is really simple.  It doesn't have an interface at all.  It just plays a sound file from a command line argument.  Thinking about it, I really need to add a 10 second length limit...  For this project to be as easy as I say it is, you'll probably want to use SDL_mixer.
Card game	Y/N	***	****	Most card game projects I've seen are 'Blackjack'.  You can make decent card games without graphics.  That's a good way to get into this stuff, but I jumped straight into a new card game project similar to Magic the Gathering.  To sum it up, I gave up on it.  I designed the card game beforehand, but I didn't actually design the computer game before I started programming it, so I was lost in a heap of messiness.
Board game	Y	***	*****	How about a board game?  I guess this one should have graphics, but the rest is up to you!  I wasn't exactly impressed by Culdcept, a fantasy board video game by Squaresoft, but it had some good ideas...
Simple platformer	Y	**	***	Start off with a really simple platformer (a jumping and running game like Super Mario Bros).  You can make one without screen scrolling (like Donkey Kong) to simplify things a lot.  Then you can keep adding stuff like items.  Don't go overboard;  You might be better off starting a new project with a full design rather than slapping stuff onto this simple one.