hm.  2.6.30-rc1 (x86_64) works OK for me.

I wonder what's different in your setup?

Just to be sure I did a clean compile of a 2.6.29.1 (download from kernel.org).
This is on a Ubuntu 8.04 Hardy.

Rebooting into the 2.6.29.1 and giving:

# echo -n 40000 > /proc/sys/kernel/pid_max 
bash: echo: write error: Invalid argument

Retrying with 2.6.30-rc2, and still having the same problem.

Could it be that Ubuntu has some sort of sysctl settings which prevents me
from raising pid_max?

Lower values work:
# echo -n 32761 > /proc/sys/kernel/pid_max

I tested 2.6.30-rc2 on x86 and x86_64.
x86_64 box can change default value to 40000 but x86 is not.

I tested some values(e.g. 32678, 32769 and so on) for pid_max. then I notice 32768 is the maximum number for x86.

Also I checked source code. 
According to sysctl.c handler and some values are defined.
.ctl_name       = KERN_PIDMAX,
.procname       = "pid_max",
.data           = &pid_max,
.maxlen         = sizeof (int),
.mode           = 0644,
.proc_handler   = &proc_dointvec_minmax,
.strategy       = sysctl_intvec,
.extra1         = &pid_max_min,
.extra2         = &pid_max_max,

You can change pid_max value which is between pid_max_min and pid_max_max.

However, pid_max_max is defined in pid.c.
int pid_max_max = PID_MAX_LIMIT;

And, PID_MAX_LIMIT is defined in linux/threads.h.
#define PID_MAX_LIMIT (CONFIG_BASE_SMALL ? PAGE_SIZE * 8 : \
        (sizeof(long) > 4 ? 4 * 1024 * 1024 : PID_MAX_DEFAULT))

I checked the PID_MAX_LIMIT value on my x86 box and it is 32768.
so, I think you cannot change pid_max more than PID_MAX_LIMIT.
I think if you use x86, your PID_MAX_LIMIT would be 32768.

oops, I should say that please check your config file like this.
[masami@moon:~]% grep CONFIG_BASE_SMALL /boot/config-2.6.30-rc2-git 
CONFIG_BASE_SMALL=0

if CONFIG_BASE_SMALL set 0, maximum  pid_mux would be 32768.

[ Quoting bugzilla-daemon@bugzilla. in "[Bug 13090] pid_max no writable in "... ]
> http://bugzilla.kernel.org/show_bug.cgi?id=13090
> 
> 
> --- Comment #5 from Masami Ichikawa <masami256@gmail.com>  2009-04-21
> 16:11:40 ---
> oops, I should say that please check your config file like this.
> [masami@moon:~]% grep CONFIG_BASE_SMALL /boot/config-2.6.30-rc2-git 
> CONFIG_BASE_SMALL=0
> 
> if CONFIG_BASE_SMALL set 0, maximum  pid_mux would be 32768.

Ah, this is indeed the case:

% grep CONFIG_BASE_SMALL /boot/config-2.6.29-020629*
/boot/config-2.6.29-02062901-generic:CONFIG_BASE_SMALL=0
/boot/config-2.6.29-020629-generic:CONFIG_BASE_SMALL=0

Thanks for your reply.

grtz Miek