You can't do it the way you imagine because you cannot call derived virtual functions from within the base class constructor—the object is not yet of the derived type. But you don't need to do this.
Calling PrintStartMessage after MyBase construction
Let's assume that you want to do something like this:
class MyBase {
public:
    virtual void PrintStartMessage() = 0;
    MyBase() {
        printf("Doing MyBase initialization...\n");
        PrintStartMessage(); // ⚠ UB: pure virtual function call ⚠
    }
};
class Derived : public MyBase {
public:
    virtual void PrintStartMessage() { printf("Starting Derived!\n"); }
};
That is, the desired output is:
Doing MyBase initialization...
Starting Derived!
But this is exactly what constructors are for! Just scrap the virtual function and make the constructor of Derived do the job:
class MyBase {
public:
    MyBase() { printf("Doing MyBase initialization...\n"); }
};
class Derived : public MyBase {
public:
    Derived() { printf("Starting Derived!\n"); }
};
The output is, well, what we would expect:
Doing MyBase initialization...
Starting Derived!
This doesn't enforce the derived classes to explicitly implement the PrintStartMessage functionality though. But on the other hand, think twice whether it is at all necessary, as they otherwise can always provide an empty implementation anyway.
Calling PrintStartMessage before MyBase construction
As said above, if you want to call PrintStartMessage before the Derived has been constructed, you cannot accomplish this because there is no yet a Derived object for PrintStartMessage to be called upon. It would make no sense to require PrintStartMessage to be a non-static member because it would have no access to any of the Derived data members.
A static function with factory function
Alternatively we can make it a static member like so:
class MyBase {
public:
    MyBase() {
        printf("Doing MyBase initialization...\n");
    }
};
class Derived : public MyBase {
public:
    static void PrintStartMessage() { printf("Derived specific message.\n"); }
};
A natural question arises of how it will be called?
There are two solution I can see: one is similar to that of @greatwolf, where you have to call it manually. But now, since it is a static member, you can call it before an instance of MyBase has been constructed:
template<class T>
T print_and_construct() {
    T::PrintStartMessage();
    return T();
}
int main() {
    Derived derived = print_and_construct<Derived>();
}
The output will be
Derived specific message.
Doing MyBase initialization...
This approach does force all derived classes to implement PrintStartMessage. Unfortunately it's only true when we construct them with our factory function... which is a huge downside of this solution.
The second solution is to resort to the Curiously Recurring Template Pattern (CRTP). By telling MyBase the complete object type at compile time it can do the call from within the constructor:
template<class T>
class MyBase {
public:
    MyBase() {
        T::PrintStartMessage();
        printf("Doing MyBase initialization...\n");
    }
};
class Derived : public MyBase<Derived> {
public:
    static void PrintStartMessage() { printf("Derived specific message.\n"); }
};
The output is as expected, without the need of using a dedicated factory function.
Accessing MyBase from within PrintStartMessage with CRTP
While MyBase is being executed, its already OK to access its members. We can make PrintStartMessage be able to access the MyBase that has called it:
template<class T>
class MyBase {
public:
    MyBase() {
        T::PrintStartMessage(this);
        printf("Doing MyBase initialization...\n");
    }
};
class Derived : public MyBase<Derived> {
public:
    static void PrintStartMessage(MyBase<Derived> *p) {
        // We can access p here
        printf("Derived specific message.\n");
    }
};
The following is also valid and very frequently used, albeit a bit dangerous:
template<class T>
class MyBase {
public:
    MyBase() {
        static_cast<T*>(this)->PrintStartMessage();
        printf("Doing MyBase initialization...\n");
    }
};
class Derived : public MyBase<Derived> {
public:
    void PrintStartMessage() {
        // We can access *this member functions here, but only those from MyBase
        // or those of Derived who follow this same restriction. I.e. no
        // Derived data members access as they have not yet been constructed.
        printf("Derived specific message.\n");
    }
};
No templates solution—redesign
Yet another option is to redesign your code a little. IMO this one is actually the preferred solution if you absolutely have to call an overridden PrintStartMessage from within MyBase construction.
This proposal is to separate Derived from MyBase, as follows:
class ICanPrintStartMessage {
public:
    virtual ~ICanPrintStartMessage() {}
    virtual void PrintStartMessage() = 0;
};
class MyBase {
public:
    MyBase(ICanPrintStartMessage *p) : _p(p) {
        _p->PrintStartMessage();
        printf("Doing MyBase initialization...\n");
    }
    ICanPrintStartMessage *_p;
};
class Derived : public ICanPrintStartMessage {
public:
    virtual void PrintStartMessage() { printf("Starting Derived!!!\n"); }
};
You initialize MyBase as follows:
int main() {
    Derived d;
    MyBase b(&d);
}