[offtopic]I much prefer FCE to Premiere and would encourage you not to switch, but that's my personal opinion.[/offtopic]

Note... this is what I use for live action, 29.97 fps footage, so how well it'll work for brickfilming, I'm not sure.

If you're exporting to edit in another program (for example, AE or Encore), use the "Export as QuickTime Movie" option. This doesn't actually create a movie file, merely a list of references to the original video clips that acts like a .mov file in certain programs. You won't be able to upload this type of .mov to YouTube, but to add effects in AE, for example, there's nothing faster, smaller, or better quality.

For exporting self-contained files, I use the "Export using QuickTime Conversion" option. Go into Options. On the Video Settings tab: Compression Type H.264, Keyframes every 24 frames, Data Rate automatic, Compressor quality slider to Best, Encoding Quality best (multi-pass). On the Video Size tab, Dimensions 1280 x 720 HD, and uncheck De-interlace Source Video. And lastly, on the main settings screen, uncheck "Prepare for Internet Streaming." These last two aren't the default settings, so make sure you get both of them.

The results aren't perfect, but they do look pretty solid, even when uploading to YouTube. However, I'll be honest and say that I haven't gone back and compared the original footage to the export to see if I have the color muting issue that your images display. I have a feeling that it's the result of your compression codec... both H.264 and NTSC-DV have done that to me when exporting from AE. If you've tried the slate of settings I listed above and you're still have the color muting issue, try Animation, None, or PNG as your compression type instead of H.264... I believe all three of those are lossless and should correct the issue.

Just be forewarned... the files will be massive. I haven't tried compressing afterwards in VirtualDub to see if image quality is lost, so that might be worth a shot if drive space is an issue.