UPDATE 1/26/2015 -- It appears the most recent JRE/JDK for Java 8 (update >= 31) and JRE/JDK for Java 7 now include the Godaddy G2 CA server in the default trust store. If possible, it's urged you upgrade your JRE/JDK to the latest Java 8 update to resolve this issue.
UPDATE 11/29/2014 -- This is still a problem, and Godaddy appears to not care nor will do anything about it. There is a blog post[here][1]by Godaddy VP of Security Products from several months ago saying a fix was on it's way and provided a temporary work-around, but as-of today nothing has changed. It is important to note that Godaddy's G2 CA server has been around for a minimum of 5 years, and in that time Godaddy has not taken the proper steps to resolve this known issue. The work-around provided is just that, a work-around, not a solution. Users of 3rd party services have zero control over how the cert is installed on the server.
It seems users should avoid purchasing Godaddy SSL certs until they get serious about being a CA.
Here is their SSL team's contact info if you feel inclined to call:
GoDaddy SSL Team Support Number: 1-480-505-8852 -- Email: ra@godaddy.com
UPDATE 9/17/2014 -- This is still a problem, and Godaddy appears to not care nor will do anything about it. Come November when Google deprecates all SHA-1 certs, this will become a major issue. I highly recommend anyone who can contact Godaddy and point them here.
~~~~
My initial post/question was regarding why my chain was not working. It became obvious I had a bad setup (which was quickly fixed with some advice from @Bruno and others - thanks). However, when my corrected chain still did not work with Java, it became apparent there was a much bigger problem lurking. It took a while, but the problem is actually with GoDaddy.
This actually is indeed a GoDaddy problem (I've had lengthy support emails with them).
They have 2 CA servers, one called Class 2 CA and the other called G2 CA. Their Class 2 CA signs all SHA-1 certificates, while the G2 CA signs all their SHA-2 certificates.
This is where the problem lies - GoDaddy has not added their newer G2 CA server to the default Java truststore/keystore - causing default Java installations to not trust it's authority, and hence, does not trust your chained certificate.
The work-around until GoDaddy adds the G2 CA server to the default truststore/keystore is to simply rekey your cert using SHA-1 as-to get a cert signed by the Class 2 CA server. Rekeying is free for GoDaddy customers until your cert expires (obviously).
Once you have a SHA-1 cert signed by the Class 2 CA server, your trust chain should work as expected and no custom truststore/keystore imports and/or setup is required.
It does not make me happy that I must use a "weaker" cert in order to get it to work properly, and discussions with GoDaddy via email support thus far have indicated they have no current plans to add the G2 CA server to the default truststore/keystore. I guess until they do add it, make sure you get a SHA-1 Class 2 CA server signed cert if you plan to work with Java.
Best Answer
Pretty much all* browsers will support 4096-bit keys. The issue you'll run into is that key exchange is slower with larger keys, which will increase load on the server and slow down page loading on the client.
2048-bit keys are generally considered safe for the time being. If you want an intermediate step, though, 3072-bit keys are right smack-dab in the middle.
*: Only exception might be a couple of weird, old mobile / embedded browsers.