Dynamic Allocation of an Array of Pointers to Objects

Can't reproduce your problem. Specifically, here's all of the skeleton code I compiled and ran successfully -- your method plus the minimal scaffolding to make it into a complete program:

#include <iostream>

struct Device {
  char* name;
  Device(char* n) {name = n;}
};

struct HealthClub {
  int NumberOfDevices;
  Device** HealthClubDevices;
  HealthClub() { NumberOfDevices = 0;}
  void AddHealthClubDevice(char *);
};

std::ostream& operator<<(std::ostream& o, const HealthClub& h) {
  o << h.NumberOfDevices << " devices:" << std::endl;
  for(int i=0; i<h.NumberOfDevices; ++i) {
    o << "  " << h.HealthClubDevices[i]->name << std::endl;
  }
  o << "That's all!\n" << std::endl;
  return o;
}

void HealthClub::AddHealthClubDevice ( char* HealthClubDeviceName )
{                                       //We added NumberOfDevices as an attribute, so we won't have to use sizeof all the time
    if (NumberOfDevices==0)  // This is for the first device we want to add
    {
        HealthClubDevices = new Device*[1];
        HealthClubDevices[0]= new Device(HealthClubDeviceName);
        NumberOfDevices++;
    }
    else        // Here we did realloc manually...
    {
        Device** tempHealthClubDevices;
        tempHealthClubDevices = new Device*[++NumberOfDevices];  //this is where we see the first sign of a problem, The tempHealthClubDevices is not allocated properly

        for (int i=0 ; i<(NumberOfDevices-1) ; i++)
         tempHealthClubDevices[i]=HealthClubDevices[i];
        delete[] HealthClubDevices;          
        HealthClubDevices = tempHealthClubDevices;
        HealthClubDevices[NumberOfDevices-1]= new Device(HealthClubDeviceName);
   }
}

int main() {
  HealthClub h;
  std::cout << h;
  h.AddHealthClubDevice("first");
  std::cout << h;
  h.AddHealthClubDevice("second");
  std::cout << h;
  h.AddHealthClubDevice("third");
  std::cout << h;
  return 0;
}

Compiles fine, even with --pedantic, and when run emits:

$ ./a.out 
0 devices:
That's all!

1 devices:
  first
That's all!

2 devices:
  first
  second
That's all!

3 devices:
  first
  second
  third
That's all!

as desired. So, your problem's cause must lie elsewhere. Given your real program which fails (you don't show us exactly how) and this minimal one which succeeds, you can "interpolate by bisection" to build the minimal failing case -- if that still doesn't show you where the problem lies, posting the minimal failing case and the one epsilon smaller than it which still succeeds as a SO question can surely get you the help you need (be sure to also specify compiler, OS, and so on).