I had a bag like the one your posted a link to for a while and got frustrated with its weight and stiff edges, making it hard to stuff in things of variable size like my BOSE headphones without putting pressure on them. It sits unused, as I have switched to a black leather Wilson's Leather computer backpack which you can wear on your back (healthier than over the shoulder), over your shoulder, or carry using the extra leather handle on top. I purchased it at the Wilson's store in MSP, you might be able to find it on-line.
I love it -- it accomodates my Powerbook in an included protective case, leaving space for my BOSE either on top there or in the wide top zipper pouch, plus it has two side pouches which hold my iPOD, a Palmpilot, snacks, then there are more side zipper compartments for pens, books, magazines, paper things, passport, and misc whatever you haven't stuffed into your jacket and pants pockets. AND on the bottom I can throw in a lightweight change of clothes (NOT a suit!) OR (not and) a small pillow.
Fully stuffed, it easily fits in all overhead compartments, and under most seats except the weird aisle seats that chop off half your legspace with the metal bars (like on some puddle-jumper planes), or the window seats which chop off your space with IFE equipment.