I've done some more digging into this for the FreeBSD case.

FreeBSD 6.3 and 7.0 both have sem_open, and the man pages suggest it 
should be fully functional. (see
http://www.freebsd.org/cgi/man.cgi?query=sem_open&apropos=0&sektion=0&manpath=FreeBSD+6.3-RELEASE&format=html)
There is a caveat on the length of the name, which I think could trigger
if the counter variable passed into SEM_CREATE() is >9999.  But as that 
variable seems like it can only ever be 0 (not sure this is intended!)
this shouldn't happen as it stands.

If I change HAVE_SEM_OPEN to 1 in setup.py, the _multiprocessing module
builds, but test_multiprocessing provokes a core dump in both cases.
The backtrace (on 6.3 i386) looks like:
#0  0x2820ef17 in ksem_open () from /lib/libc.so.6
#1  0x2820592c in sem_open () from /lib/libc.so.6
#2  0x284494a0 in semlock_new (type=0x2844b380, args=0x836443c, kwds=0x0)
    at
/home/andymac/build/python-svn/trunk-r66550/Modules/_multiprocessing/semaphore.c:439
#3  0x0809e710 in type_call (type=0x2844b380, args=0x836443c, kwds=0x0)
    at Objects/typeobject.c:731
#4  0x0806042a in PyObject_Call (func=0x2844b380, arg=0x836443c, kw=0x0)
    at Objects/abstract.c:2487
#5  0x080cc367 in PyEval_EvalFrameEx (f=0x84dd00c, throwflag=0)
    at Python/ceval.c:3890
#6  0x080cf9ac in PyEval_EvalCodeEx (co=0x8478800, globals=0x4e,
locals=0xa00,
    args=0x819b02c, argcount=4, kws=0x0, kwcount=0, defs=0x0, defcount=0,
    closure=0x0) at Python/ceval.c:2942
#7  0x08123f84 in function_call (func=0x8486ca4, arg=0x82e107c, kw=0x0)
    at Objects/funcobject.c:524
#8  0x0806042a in PyObject_Call (func=0x8486ca4, arg=0x82e107c, kw=0x0)
    at Objects/abstract.c:2487
#9  0x08069c15 in instancemethod_call (func=0x4e, arg=0x82e107c, kw=0x0)
    at Objects/classobject.c:2579
#10 0x0806042a in PyObject_Call (func=0x84857ac, arg=0x82e107c, kw=0x0)
    at Objects/abstract.c:2487
#11 0x080cc367 in PyEval_EvalFrameEx (f=0x826140c, throwflag=0)
    at Python/ceval.c:3890
---Type <return> to continue, or q <return> to quit---

On 7.0 amd64, the top of the backtrace scrolls off screen so I can't get 
the start of the trace (X not installed...).

To try and remove threads from the equation, due to FreeBSD 6.3 having 
an issue with fork() in a threaded build (see issue3864 for more info), 
I configured without threads (ie ./configure --without-threads) and 
the _multiprocessing module fails to build:

gcc -fPIC -fno-strict-aliasing -DNDEBUG -g -fwrapv -O3
-Wall-Wstrict-prototypes -DHAVE_SEM_OPEN=1 -DHAVE_FD_TRANSFER=1
-DHAVE_SEM_TIMEDWAIT=0 -IModules/_multiprocessing -I.
-I/home/andymac/build/python-svn/trunk-r66550/./Include -I. -IInclude
-I./Include -I/usr/local/include
-I/home/andymac/build/python-svn/trunk-r66550/Include
-I/home/andymac/build/python-svn/trunk-r66550 -c
/home/andymac/build/python-svn/trunk-r66550/Modules/_multiprocessing/semaphore.c
-o
build/temp.freebsd-6.3-RELEASE-i386-2.6/home/andymac/build/python-svn/trunk-r66550/Modules/_mult
iprocessing/semaphore.o
/home/andymac/build/python-svn/trunk-r66550/Modules/_multiprocessing/semaphore.c:
In function `semlock_acquire':
/home/andymac/build/python-svn/trunk-r66550/Modules/_multiprocessing/semaphore.c:314:
error: `_save' undeclared (first use in this function)
/home/andymac/build/python-svn/trunk-r66550/Modules/_multiprocessing/semaphore.c:314:
error: (Each undeclared identifier is reported only once
/home/andymac/build/python-svn/trunk-r66550/Modules/_multiprocessing/semaphore.c:314:
error: for each function it appears in.)

It appears that some support is there for a single threaded build, but
is incomplete (there's a similar problem in socket_connections.c, but
the module build bails before then).

If its not to be supported on single threaded builds (which would be a
big shame in my opinion!) then the code should make this explicit,
otherwise the single threaded build case needs to be fixed.

I'm still trying to understand the core dump in the multithreaded build
- unfortunately I'm not terribly familiar with gdb or with debugging
from cores (and the actual failure appears to be triggering in the C
library for which I currently don't appear to have symbols...)

Any suggests on how/where to dig further on this?