EDIT: Similar symptoms in another instance were solved by UNINSTALLING the Android client and then rebooting the phone and reinstalling the latest version.
Most of these issues are fixable, but it may take some troubleshooting.
1st: The current Android client is now 2.1
Subsonic versions 4.1 and 4.2 are both very stable when properly set up.
The fact that you can connect to the demo without problems indicates that your problem is most likely on the server and not the phone. The demos server only has 128kbps music on it, so to be sure test your phone(s) on my server at
http://maplegrove.subsonic.org username and password guest. look for some tracks that are 256kbps of higher to make sure your phone works with higher bit rate music.
Assuming your phone tests well, you then need to focus on the server setup. What version of SS are you running? Do you have the latest version of Java installed? On systems with 64 bit browsers you want both 32 & 64 bit Java properly installed. If you suspect that Subsonic is not properly installed, shut down the service, remove the SS directory , and reinstall the latest version.
If a clean SS install still doesn't solve the problem, the issue most likely lies in the network/firewall configuration. I always recommend that the server be assigned a static ip on the network, prefferably at the upper end of the range, e.g. 192.168.1.254, so that it is out of the way of router DHCP. Once you've defined the static route in the router, define the same ip settings on the NIC of the server.
Next check the port number used bu SS. Never use port 80 as many isp's either block it or use it for remote management of the gateway device. 8080, 8081, etc. usually work fine. The final step is to define the port forwar in the router to SS. Make sure that in the settings/network section on Subsonic that the first box "Automatically configure your router to allow incoming connections to Subsonic (using UPnP or NAT-PMP port forwarding)" is UNCHECKED. Although I'm sure some have used the auto setup successfully, I never depend on uPNP to do the setup. Most often it doesn't work, and more importantly, you need to understand the network settings to effectively maintain your network. Good luck, let me know if you run into trouble.