I have been trying for days to get a computer to recognise my Uno with no luck. I have tried it on Mac Mavericks, Ubuntu and Windows 8. How would I check if it is the board or whether it is to do with my setup?
When you run lsusb in Ubuntu, connect the Arduino and run lsusb once more you should see the board. It if doesn't, there is something wrong. Is it an official board you just bought ?
When it is faulty or doesn't have a bootloader, return it. Get a new one.
You can burn a new bootloader, when you have a programmer. But that is for advanced users. When there is no com-port at all, burning the bootloader might not be enough. I use a USBasp programmer, and in such situations there is perhaps 50% chance that a new bootloader will help.