My son is 4.5 and we started it in January this year. We totally love it. He has done 40 lessons so far (the first four maps) and gotten 85-100% on every quiz, walks around sounding out words, and remarking on what their first letter sound is and naming the letter. He begs to do ReadingEggs. We do it 2-4 evenings a week, 1-2 lessons a night.
We also have the first set of 40 books, flashcards, the workbooks, maps and stickers, and I find this to be invaluable review. Again he loves it.
I wrote blogposts about it here:
http://wenjonggal.wordpress.com/2010/01/19/hatching-a-reader-with-readingeggs/