USB 1.1 is more than enough.
From the dmesg I can conclude your computer does not see the device at all (just to make sure: did you plug it in in powered on state?) - try another USB cable and then another computer to figure out what exactly is broken.
For the reference, Linux output the following lines to the log when something like V3 is attached:
Code:
[763343.412071] usb 3-1: new full speed USB device using uhci_hcd and address 3
[763343.618604] usb 3-1: New USB device found, idVendor=0525, idProduct=a4a2
[763343.618613] usb 3-1: New USB device strings: Mfr=1, Product=2, SerialNumber=0
[763343.618619] usb 3-1: Product: RNDIS/Ethernet Gadget
[763343.618624] usb 3-1: Manufacturer: Linux 2.6.29-v3 with s3c2410_udc
[763343.618830] usb 3-1: configuration #1 chosen from 2 choices