A 32-bit address space means that you have space for 4GB of addresses. Ideally the kernel likes to be able to map all physical memory, all the memory of the current task, and all of its own memory. If physical memory alone takes up all of the available 4GB, that won't work. So physical memory is divided into low memory, which is mapped all the time, and high memory, which must be mapped when in use. Unless you're running a patched kernel, on the ix86 architecture, 128MB of address space is devoted to kernel code and data structures, and 896MB is devoted to mapping physical memory (for a total of 1GB).
Background reading on the complexities of memory management when your address space isn't comfortably larger than your total memory:
Excerpts from your kernel logs:
BIOS-provided physical RAM map:
BIOS-e820: 0000000000000000 - 000000000009f800 (usable)
BIOS-e820: 000000000009f800 - 00000000000a0000 (reserved)
BIOS-e820: 00000000000f0000 - 0000000000100000 (reserved)
BIOS-e820: 0000000000100000 - 00000000cdce0000 (usable)
BIOS-e820: 00000000cdce0000 - 00000000cdce3000 (ACPI NVS)
BIOS-e820: 00000000cdce3000 - 00000000cdcf0000 (ACPI data)
BIOS-e820: 00000000cdcf0000 - 00000000cdd00000 (reserved)
BIOS-e820: 00000000d0000000 - 00000000e0000000 (reserved)
BIOS-e820: 00000000fec00000 - 0000000100000000 (reserved)
BIOS-e820: 0000000100000000 - 0000000130000000 (usable)
2404MB HIGHMEM available.
887MB LOWMEM available.
Zone PFN ranges:
DMA 0x00000000 -> 0x00001000
Normal 0x00001000 -> 0x000377fe
HighMem 0x000377fe -> 0x000cdce0
Here you have 887MB of low memory: the theoretical maximum of 896MB minus a few MB of DMA buffers (zones of memory used to communicate with hardware devices).
Of your physical memory, 3328MB is mapped at addresses below 4GB and 768MB is mapped at addresses above 4GB (the 0x100000000–0x130000000 range). You're not getting access to these 768MB, which explains why you only have 3242MB available (4096MB of RAM minus 768MB inaccessible minus 9MB of DMA buffers minus 75MB used by the kernel itself for code and data). I don't know why the BIOS maps some RAM above the 4GB mark, but as a data point, I'm posting this from a PC with 4GB of RAM that similarly has RAM mapped at 0x100000000–0x130000000.
Mapping physical memory above 4GB requires using PAE. PAE incurs a small performance overhead (in particular, it requires bigger data structures in the memory manager), so it's not systematically enabled. The default Ubuntu kernel is compiled without PAE support. Get the
-generic-pae kernel to be able to access up to 64GB of RAM.
TL,DR: Linux is working as expected. The firmware isn't so helpful. Get a PAE-enabled kernel.