I think you should be using RGB complements (in the "Light" answer). The RYB complements were from an era when people didn't know of light's primary colors being RGB. RGB complements look nicer, in my opinion. Here's some random person's (Lira) post (perhaps someone can give me a more credible source?):
RYB is the traditional colour wheel,
used by artists. Sir Isaac Newton was
the first one to come up with this
sort of thing. And it was kind of fun.
Here, take a look:

Recognise it? It's the colour wheel
Jason Beaird used in his "Color for
Coders" article. Remember that, when
we're in kindergarten and stuff, we're
taught stuff like "Yellow plus Red
equals Orange"? It all comes from this
colour wheel, whose primary colours
are red, yellow and blue (they're
touching the darker triangle, poiting
upwards). Warm colours occupy half of
the space and cold colours the other
half. That's like a colour Yin Yang.
Almost too perfect to be true.
Indeed, it was too perfect to be true.
Scientists then find out that
biologically, it doesn't really work
that way. Anyway, after studying,
researching, analysing, chopping and
cooking colours, we ended up having
the RGB colour model, ubiquitously
present in stuff like computer
monitors, TV's and so on.
As you might be assuming, the colour
wheels are a bit different. The
opposite of "red" in the RYB colour
wheel is "green", whereas the opposite
of "red" in the RGB colour wheel is
cyan - you can test the latter by
staring at something red (focus, try
not to blink) and then looking at a
white surfice: the afterimage is cyan.
Here's an example:
http://faculty.washington.edu/chudler/after.html
That means you have two different
colour wheels to choose your colours
from. So, which one of them do you
guys prefer?
Light:
The definition of a complementary color is this:
if color = {"RR", "GG", "BB"}
then color.complement = {FF - "RR", FF - "GG", FF - "BB"}
Meaning:
if color = {12, 4A, FF}
then color.complement = {FF - 12, FF - 4A, FF-FF}
Calculating the values:
color.complement = {ED, B5, 00}
That's it. Adobe is wrong; they're probably giving you something that "looks nice", in their opinion - NOT the true complement.
Or, if you're lazy, you'll simply do this:
color = 124AFF
color.complement = FFFFFF - 124AFF
color.complement = EDB500
Microsoft Calculator Plus or Windows7 Calculator (both in Programmer Mode) can do this for you.
Here, I made a small quick web "app": http://jsfiddle.net/rXsAT/
Looks like someone already made a nicer version.
Pigments:
Working on it...
Perhaps it's:
{FF - RR, FF - (RR + BB)/2, FF - BB} ???
Gotta do my homework, I'll work on it tomorrow.
Test cases (for me):
Red FF0000 vs Green 00FF00
Blue 0000FF vs Orange FF7F00
Yellow FFFF00 vs Violet 6F00FF
(Purple is 800080 or 7F007F, which is better, I think...?)