I just went through a 2 month ordeal with my 24" iMac. The graphics started going wacky and locking up the machine more and more frequently. I finally took it in just before Thanksgiving week since I was going to be gone anyway. They replaced the graphics card, logic board and display. When I got the computer back, the CPU fan would ramp up for no reason to over 3000 rpm with little to no load on the CPU. I was very busy and couldn't bring it in right away. I finally brought it in a few weeks back. They said it was probably a USB device I was using going bad. So I carried it back home and tried using it with just the Apple keyboard and mouse. I was able to make the fans race with nothing running but a Beatles video on the Apple homepage. They were throwing crap at me about flash this and that so i wanted to use something from their own page. So I brought it back in and they decided to replace the fan and temp sensor (the ambient temp reading would jump from 18C to 26C in one cycle and then back to 22...) About 4 or 5 days later they called and said it was ready. I went in and made them turn it on in the store. I did the same thing, went to their page and let the Beatles video play. Within a few minutes, the fan was racing with 3-5% CPU load. The tech asks if he can reinstall the OS. I said that's fine. He calls the next day and said it's still doing it. They thought it was a bad logic board so they wanted to replace that again. That was a few days before Christmas and I was upset because I wanted to get the computer with a blank OS back up and running over the long weekend. A few more phone calls checking for updates and finally on Tuesday evening they called and said I could come get a new computer.
You may need to be a bit patient, but Apple will make it right. Especially if you have Applecare I think. My 24" was just under 2 years old. I threw in the difference and upgraded to the i7. They were going to give me the base 3.2 GHz 27".
I did call Applecare at one point and they said if I wanted to talk to a supervisor they may decide to offer a replacement but I'd have to wait for it to ship. I decided to wait it out with my local store.
Good luck and I hope you are able to get them to replace it.