Domanda: quanti elementi contiene tabella? Risposta: nemmeno uno.
codice:
std::vector<std::vector<Casella*>> *tabella = new std::vector<std::vector<Casella*>>();
Corretto sarebbe:
codice:
std::vector<std::vector<Casella*>> *tabella = new std::vector<std::vector<Casella*>>(n);
e nel costruttore di tabella:
codice:
    for (int i = 0; i < n; i++) {
        tabella->at(i).resize(n);
        etc...
Tuttavia non capisco perché devi complicarti la vita in questo modo con i puntatori (a meno che sia una precisa consegna).
Più semplice sarebbe:
codice:
class Tabella
{
private:
    int n;
    std::vector<std::vector<Casella>>;


public:
    
    Tabella(int nelem); /*Crea Tabella di Default a 0*/
    ~Tabella();
    void mostraSudoku();
    void esisteSuRiga();
    void esisteSuColonna();
    void esisteInRegione();
};


/*Crea Tabella di Default a 0*/
Tabella::Tabella(int nelem) : n(nelem)
{   
    tabella.resize(n);    
    for (int i = 0; i < n; i++)
    {
        // crea una riga di caselle usando il costruttore di default 
        tabella.at(i).resize(n);
    }
};


Tabella::~Tabella()
{
    // niente da fare perché ci pensa in automatico il distruttore dei vector
}

....
int _tmain(int argc, _TCHAR* argv[])
{
    int size = 0;
    std::cout << "Inserisci il size di riga e colonna della Cella: " << std::endl;
    std::cin >> size;
    Tabella tabella(size);
    tabella.mostraSudoku();
    system("PAUSE");
    return 0;
}