Hi
I'd say it's your video card and not logic board.
I had the exact same problem with green dots on my PowerMac G4 Sawtooth with Radeon 9000. They'd sometimes move around the screen too and cause random freezing especially in games (where the green squares were large and would wrap around the 3D objects).
They were scattered all throughout the OS GUI, I ended up changing the video card back to the stock rage 128 and that fixed things (although I could no longer run leopard "semi smoothly").
A few days ago I tried changing it back to the broken 9000 but the green dots once again appeared.
So unfortunately sending back to Apple sounds like your only option as you can't replace your video card yourself (I think thats still the case even with the new graphics socket on the latest iMacs)
EDIT:
Well we just got it a month ago so we should right? Should I restore before we go?
Yes you will be covered if you are within your first year of regular warrenty, or within your first 3 years of Applecare.
I'd recommend you backup before you take your machine in. When you say restore I'm not sure what you mean, but if you mean wiping everything I think it's necessary, just delete any personal info.