Just did a jailbreak via redsnow on my iPad 1 and now App Store is saying it can't connect to iTunes store. Tried restarting device, resetting network settings, etc but all failed. Has anyone experienced this before?

Did you try the old standards: close out the app and then restart or reset the iPad? To do (apologies if you already know):

Fully Close an App: Double tap the Home button (or do a 4-finger swipe up) to reveal a row of icons in the multi-tasking bar. Press and hold an icon until they all start to wiggle and you see a red circle with a minus sign ("-") in the top left. Press the minus sign to fully close the app. Don't worry, it won't remove the app from your iPad, just from the iPad's resident memory.

Then...
Restart: Hold down the power button until the power off slider appears. Slide it off. When the iPad finishes shutting down, hold down the power button again until the Apple logo appears.

If that doesn't help, try this last step...

Reset: Hold both the power and home buttons until the screen goes dark and the Apple logo then appears (the slide to unlock screen may or may not appear). Once the logo appears, release the buttons. After a time, your homescreen will appear. Please note that it may take some time for the Apple logo to appear or for your homescreen to appear (or both). This is normal. Eventually, the homescreen will appear.

If none of that helps, holler back and we'll take another shot at it. Good luck.

Marilyn