I'm on Elementary OS Luna currently but I tried the same on Ubuntu before and it didn't work. I tried both AP hotspot and various other guides using hostapd but none of them seem to work with android I either get a message that the connection is poor or it connects but doesn't share internet. I'm using a wired dial up connection. If you need me to run any commands and post the output just post them.