Det er fordi at et program som udgangspunkt kun kører i en tråd. Tråde er en måde at håndtere sine arbejdsopgaver, så dit interface ikke fryser - eller rettere så dit program kan multitaske.
Det er lidt grynet at komme i gang med de første par gange... for andre tråde må ikke direkte manipulere ting der ikke tilhører ligepræcis den tråd, og da slet ikke ting i GUI.
Skriver lige et eksempel, kan ikke rigtig benytte dit uden at se resten... men altså: 
-  using System;
-  using System.Collections.Generic;
-  using System.ComponentModel;
-  using System.Data;
-  using System.Drawing;
-  using System.Linq;
-  using System.Text;
-  using System.Windows.Forms;
-  
-  //Threading namespace!
-  using System.Threading;
-  
-  namespace WindowsFormsApplication1
-  {
-      public partial class Form1 : Form
-      {
-          private delegate void ThreadCallBack(int row, int cell, Color c);
-  
-          public Form1()
-          {
-              InitializeComponent();
-  
-              ColorCells();
-          }
-  
-          //Opretter nu tråd der arbejder sig igennem rækkerne
-          public void ColorCells()
-          {
-              ThreadStart starter = delegate { BGWorker(this.dataGridView1.Rows); };
-              Thread t = new Thread(starter);
-              t.Start();
-          }
-  
-          //Metoden til baggrundstråden
-          public void BGWorker(DataGridViewRowCollection rows)
-          {
-              ThreadCallBack callback = new ThreadCallBack(ColorRow);
-              
-              foreach (DataGridViewRow row in rows)
-              {
-               //alle dine betingelser skrevet om
-               
-               
-                  for (int i = 0; i < row.Cells.Count; i++)
-                      this.dataGridView1.BeginInvoke(callback, row.Index, i, System.Drawing.Color.ForestGreen);
-              }
-          }
-  
-          //Callback metode der skal opdatere gui
-          public void ColorRow(int row, int cell, Color color)
-          {
-              this.dataGridView1[row, cell].Style.BackColor = color;
-          }
-      }
-  }
Det skal lige siges, at jeg på tråds af baggrundstråde har oplevet ekstreme responstider pga. hyppig opdatering af gui, hvor jeg farvede rækkerne - det foregik dog lidt anderledes - og optil 10-20 gange i sekundet, hvis ikke mere..
NB: Har ikke testet eksemplet