kernel.ubuntu.com/~jj/linux-image-2.6.31-11-generic_2.6.31-11.38_amd64 works for me.

I tested this with this profile initially:

$ cat /etc/apparmor.d/bin.nc.openbsd# Last Modified: Thu Oct  8 11:08:32 2009
#include <tunables/global>

/bin/nc.openbsd {
  #include <abstractions/base>

}

$ nc -l 10000
nc: Permission denied
[1]

and in /var/log/audit/audit.log:
type=APPARMOR_DENIED msg=audit(1255018273.352:37): operation="socket_create" pid=4468 parent=3435 profile="/bin/nc.openbsd" family="inet" sock_type="stream" protocol=6


Then I used aa-logprof:
$ sudo aa-logprof /bin/nc.openbsd 
Reading log entries from /var/log/audit/audit.log.
Updating AppArmor profiles in /etc/apparmor.d.
Enforce-mode changes:

Profile:        /bin/nc.openbsd
Network Family: inet
Socket Type:    stream

 [1 - #include <abstractions/libvirt-qemu>]
  2 - #include <abstractions/libvirt-qemu.dpkg-dist> 
  3 - #include <abstractions/nameservice> 
  4 - network inet stream 

(A)llow / [(D)eny] / Audi(t) / Abo(r)t / (F)inish

Profile:        /bin/nc.openbsd
Network Family: inet
Socket Type:    stream

  1 - #include <abstractions/libvirt-qemu> 
  2 - #include <abstractions/libvirt-qemu.dpkg-dist> 
  3 - #include <abstractions/nameservice> 
 [4 - network inet stream]

(A)llow / [(D)eny] / Audi(t) / Abo(r)t / (F)inish
Adding network access inet stream to profile.

= Changed Local Profiles =

The following local profiles were changed.  Would you like to save them?

 [1 - /bin/nc.openbsd]

(S)ave Changes / [(V)iew Changes] / Abo(r)t
Writing updated profile for /bin/nc.openbsd.

$ nc -l 10000
(it worked)


I then removed the profile and used aa-genprof:
$ sudo apparmor_parser -R /etc/apparmor.d/bin.nc.openbsd
$ sudo rm /etc/apparmor.d/bin.nc.openbsd
$ sudo aa-genprof nc
Writing updated profile for /bin/nc.openbsd.
Setting /bin/nc.openbsd to complain mode.

Please start the application to be profiled in 
another window and exercise its functionality now.

Once completed, select the "Scan" button below in 
order to scan the system logs for AppArmor events.  

For each AppArmor event, you will be given the  
opportunity to choose whether the access should be  
allowed or denied.

Profiling: /bin/nc.openbsd

[(S)can system log for SubDomain events] / (F)inish
Reading log entries from /var/log/audit/audit.log.
Updating AppArmor profiles in /etc/apparmor.d.
Complain-mode changes:

Profile:        /bin/nc.openbsd
Network Family: inet
Socket Type:    stream

 [1 - #include <abstractions/libvirt-qemu>]
  2 - #include <abstractions/libvirt-qemu.dpkg-dist> 
  3 - #include <abstractions/nameservice> 
  4 - network inet stream 

[(A)llow] / (D)eny / Audi(t) / Abo(r)t / (F)inish

Profile:        /bin/nc.openbsd
Network Family: inet
Socket Type:    stream

  1 - #include <abstractions/libvirt-qemu> 
  2 - #include <abstractions/libvirt-qemu.dpkg-dist> 
  3 - #include <abstractions/nameservice> 
 [4 - network inet stream]

[(A)llow] / (D)eny / Audi(t) / Abo(r)t / (F)inish
Adding network access inet stream to profile.

= Changed Local Profiles =

The following local profiles were changed.  Would you like to save them?

 [1 - /bin/nc.openbsd]

(S)ave Changes / [(V)iew Changes] / Abo(r)t
Writing updated profile for /bin/nc.openbsd.

Profiling: /bin/nc.openbsd

[(S)can system log for SubDomain events] / (F)inish
Setting /bin/nc.openbsd to enforce mode.
Reloaded SubDomain profiles in enforce mode.
Finished generating profile for /bin/nc.openbsd.

$ cat /etc/apparmor.d/bin.nc.openbsd
# Last Modified: Thu Oct  8 11:15:20 2009
#include <tunables/global>

/bin/nc.openbsd {
  #include <abstractions/base>

  network inet stream,


}

And this works as expected:
$ nc -l 10000