I also have this problem with Ubuntu 10.04 on multiple machines, as well as later versions [have to check which].
Observations
(1) There are two sets of 'random' strings that can be seen as supposedly sent - you can see those as an error command when you actually open the serial console ('screen /dev/ttyUSB0 115200') and press enter.
(2) If you open up the serial console immediately after power on then there is no problem with the boot process.
(3) Resetting via reset button has no problem.
Thoughts
(1) Carambola2 board has the #RESET line of the FT232RQ tied to 5V, even the FTDI references don't have this connected even though they say it can be connected... based on (3) above
(2) Can it be a buffer overrun thing? If the C2 bootloader sends too much data before the 'Press any key to halt boot' with the serial console not yet opened... based on (2) above
(3) It would be nice if the bootloader looked for a specific key or a key sequence to stop boot...
(4) Would be interesting to power a Carambola2 from another Carambola2...
I can probably test the (1) Thought if gedass or someone from 8devices can confirm which is the 4.7kOhm resistor connecting #RESET to 5V... I presume it is the 'big thing' next to U1/FB1/J14...
Would be better if 8devices tests it though