I'm using Ubuntu 12.04 x64 on an Acer Aspire 5740 laptop (i3 with HD graphics) and I too had this problem. Neither Banshee, Rhythmbox or any other program worked to put songs in my iPod Touch 4g (iOS 5.1.1 jailbroken). Installing iTunes through Wine didn't work either (i tried all versions 32 and 64 bit). I also tried to install Windows 7/XP (32 and 64 bit) through VMWare Player and Virtualbox with no success. I was about to format my laptop and install Windows 7 x64 but I kept looking and googgling for another possibility to put songs in my iPod Touch 4g and I finally found a solution that works for me. In order for this to work you need to Jailbreak your iPod touch first.
When I plug in my iPod in Ubuntu (I use 12.04 64 bit) it mounts it and it appears as a device (like a hard drive) and you can open it and navigate through the archives. You can add and delete files just like a hard drive. Well what I did was copy the mp3s that I wanted to the folder Downloads located at /var/mobile/Media/Downloads. Then, in my iPod Touch, I downloaded and installed the app MewSeek from Cydia (source: cydia.xsellize.com). MewSeek allows you to add mp3s to the iPod library when you put them in /var/mobile/Media/Downloads or by downloading them through MewSeek itself. When you put the mp3s in /var/mobile/Media/Downloads they appear in the downloads section in MewSeek. To add an mp3 to the iPod library you have to select the mp3 (or mp3s) by tapping on it/them and then tapping on the Add to iPod button on the top right corner. Then you can open the iPod app and you'll see that the mp3 (mp3s) is/are there. Also, before adding them you can edit the tags for artist, song, album, etc. in MewSeek by tapping on the mp3 and tapping on the button Edit tags on the bottom left corner. I think you can also edit the tags and even add the proper artwork using Banshee and Rhythmbox before moving the mp3s to Downloads.
Well, for me this has been the only solution to adding mp3s to the iPod app in my jailbroken iPod Touch 4g. I don't know if it works for other iPods or iPhones, i hope it does since switching back to Windows, with all due respect, would really suck! Good luck.