Objective-C retain / release snippet
Alright, there's a number of simplifications to the Utility Class I'd like to make before I continue:

Your abstraction from arc4random (at least that's what I hope it is), is too expensive to not just use the corresponding C-code directly.  You could even make your own method in C, and use the inline qualifier for faster code than calling out to a singleton 3 times for every color.  Also, it is never good to name an Objective-C method "instance".  Singletons usually use a naming convention that makes sense with their overall implementation (i.e. NSFileManager.defaultManager).  The following will generate a random double for you between 0 and 1.  Not only is it cleaner, but it's cheaper.

#define ARC4RANDOM_MAX      0x100000000
float l_fRandomRedColor = ((double)arc4random() / ARC4RANDOM_MAX);


*As an aside, it's also a good idea to use an alpha value of 1.0f, instead of 255, because alpha is also measured on a 0-1 scale


  Question A)
  
  My instance variable is released in the dealloc method. Is a the
  correct way to go?


The rule in ObjC is "You own it, you destroy it."  Because mpCurrentPieceColor is an explicitly retain'ed property, you own it.  If you were to not destroy mpCurrentPieceColor in -dealloc, then your class would retain a valid reference to it, and it simply would not go away. (memory leak).

*As an aside, switching to ARC will alleviate all of these headaches.


  Question B)
  
  Now, let's imagine I have an array, like this:
  
  UIColor* mBoardColors[WIDTH][HEIGHT];...


So long as you initialize the members of the multi-dimensional array, this is correct, but definitely not optimal.  Objective-C has it's own array objects, which free you from having to make these ridiculous memory management decisions, and a dynamic, expandable multidimensional array is as simple as nesting NS(Mutable)Arrays:

[NSMutableArray arrayWithObjects:[NSArray array],[NSArray array],[NSArray array],[NSArray array],..., nil];


Not only that, but if you were to decide to expand or contract the board at any time, you could add or remove objects at a whim, and, so long as you release any references to the objects you put into the array, when the main array is released, it will release the sub-arrays, and the sub-arrays will release their objects.  It really is quite beautiful.


  Question C)
  
  What if I want to move a color from a cell to another (moving, not
  copying), is it correct to do it like that?


Another beauty of NSArrays is the ability to swap-out objects into a new index of the array, so long as you don't exceed the array's bounds.  See the "Replacing Objects" section of NSMutableArray's documentation.  Again, as above, memory management is vastly simplified with an NSArray, than dropping down to a multi-dimensional literal.