And yes, that code works, mind to explain the structure please?
Hmm, I'm not sure I can explain it in a clear way because this is a subtle and tricky problem. Put simply, my hunch was that the problem came from your use of isdigit() directly as a template argument type.
If your compiler declares a library function with C linkage, like isdigit() in this case, you can't use it as a template argument type because functions with C++ linkage are expected. The linkage difference includes things like name mangling that make a function with C linkage hard to use safely, so I guess they just don't allow it.

My solution was to create a function object with guaranteed C++ linkage and have it return a call to isdigit().
There's nothing special about a structure, anything that forces C++ linkage to a function-like thing works just as well. You could also do it with just a regular C++ function for example.
#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int predicate( int x )
{
return isdigit( x );
}
int main()
{
string foo = "123";
if(count_if(foo.begin(), foo.end(), predicate) == foo.size())
{
cout << "\nGreat!\n";
}
cin.get();
}
In a perfect world, the reason VC++ worked fine is because isdigit() is declared with C++ linkage for that example. Here in the real world, VC++ probably just got it wrong.
Oh, and isdigit() is declared in <cctype>, not <cstdlib>.