I am just a little more concerned now because he seems like he is trying and something isn't clicking.
It's normal for it not to be clicking at this age. There's a reason that historically kids weren't taught to read until age 6 (don't get me started on recent trends), and in some high-literacy European countries they aren't taught to read until age 8 or 9. There's a maturational thing that has to happen in a brain before the visual/attentional system can figure out what to do with all those little loop-de-loops on the page. Age 4 is simply too young to be deciding it's dyslexia. More likely, he simply isn't reading-ready yet.
I think we parents of gifties tend to freak ourselves out a little about things like this. We're so used to our kids being way out ahead of the curve that them being merely normal in some area looks really weird to us.
My own 4-year-old is on track to have a larger vocabulary than her kindergarten teacher (I exaggerate only slightly), but she is hopeless when it comes to small-scale spatial stuff like puzzles, and she's showing no signs of being an early reader. I periodically have to remind myself not to worry. Her visuo-spatial skills aren't behind, they're normal.
