Is it normal that I can't connect with psexec to run a command as a local administrator from one Windows 7 machine to another without disabling the firewall?
Yes. A firewall is meant to block connections, and if configured to do so, will block connections from programs you would otherwise want unblocked. Being an administrator doesn't give you any special exemption from firewall rules unless your firewall rules are configured to apply differently to admins versus users, which is possible but not the default configuration.
What setting should I change to allow psexec to work?
On the machine you want to remotely access with PsExec, enable the following Inbound firewall rules in the predefined File and Printer Sharing group:
With these rules enabled, users with Administrative permissions on the machine will be able to issue commands remotely via PsExec.