seteuid fails even when all UIDs are 0

Question

I have some C++ code on a Linux machine whose purpose is to run some code as an arbitrary user.

#include <sys/capability.h>
#include <unistd.h>

void doAsUser(uid_t uid) {
    if (CAP_IS_SUPPORTED(CAP_SETUID)) {
        cout << "Do we have CAP_SETUID? " << cap_get_bound(CAP_SETUID) << endl;
    } else {
        cout << "CAP_SETUID not supported!" << endl;
    }

    uid_t ruid, euid, suid;
    getresuid(&ruid, &euid, &suid);
    cout << "UIDs: " << ruid << " " << euid << " " << suid << endl;

    // assume credentials of user
    status = seteuid(uid);
    if (status < 0) {
        cerr << "FATAL ERROR: Couldn't set uid: " <<  strerror(errno) << endl;
        exit(1);
    }

    // do stuff here...

    // re-assume credentials of program
    status = seteuid(my_uid);
    if (status < 0) {
        cerr << "FATAL ERROR: Couldn't reset uid: " <<  strerror(errno) << endl;
        exit(1);
    }
}

However, without fail, you get the following output when this function is run:

$ sudo ./program

...

Do we have CAP_SETUID? 1
UIDs: 0 0 0
FATAL ERROR: Couldn't set uid: Operation not permitted

What's going on here? I thought things running as root (you know, with UID 0 and CAP_SETUID) could assume effective UIDs of any other user.

EDIT: This question does not adequately answer my problem, because, as it states, "In order to perform the call to seteuid even though the EUID at the time is not 0, the SUID must be 0". My SUID is 0, my CAP_SETUID is 1, and I have no other security framework in place.