If the phone supports the function, can you try pinging the https site from the android and kindle? I am curious if there will be any sort of response. This should help narrow down whether it is a connectivity issue. Also, is it all https sites that you are experiencing issues with on the Kindle and Android or only certain secure sites? Have you tried running different browsers on the Android and Kindle to see if that helps at all? Does your router offer any sort of logging functions? Perhaps there will be a "Blocked Traffic" option to see if for whatever reason the router is blocking connections.
Sort of an odd problem you have here, but I look forward to hearing back. I don't have any ideas off the top of my head as to what is causing this, but hopefully these answers will narrow it down a little better so we can take a better crack at it. Best of luck anyhow - Sub