I'd like to thank you for your post. It induced me to tackle the problem myself, using Haskell. Like you, I didn't push my analysis far enough, though I did take one more step by noticing that the first/last digit of a palindrome whose square is palindrome can't be bigger than 3. That was enough to determine the values in [1, 10^14] within the time constraints. (The next step is to carry through the proof that none of the digits can be > 3, and thence notice the sum-of-squares constraint.)
After peeking at the analysis Google posted, it wasn't too difficult to get the time for compiled Haskell on the input file with values up to 10^100 down into the seconds range... and trying to push things further turned up a way to calculate the counts for certain intervals without having to generate the palindromes. Current execution time is a bit under 0.8 seconds, so I'm sure that even interpreted it would easily meet the Code Jam time constraints.
I'm not claiming to be a great programmier; I looked up the integer square root algorithm, I am sufficiently unfamiliar with the portion of Haskell that does I/O that I cribbed from a contestant's Main (so even if the preliminary round weren't over I wouldn't have submitted it), and the final code is the result of two or three weeks of coding and debugging in my spare time, though Haskell and ghci certainly made the debugging easier. (And not quite final version, to be honest; I want to try keeping generated palindromes in a balanced binary search tree.) But if this problem is any indication, Code Jam's intent is to push contestants to quickly come up with the better, lower time-complexity methods. I'm not there yet, but with work, I hope to get there, and I have you to thank for it in part. Thanks.