If you can ping through the linux router from one VLAN to another then this would suggest that routing is working correctly.
I would check whether the Linux machine is using IP chains or similar which i believe is software that provides a firewall function and could potentially be blocking various ports.
How many VLANs are you routing between, the reason i ask is that you mentioned 802.1q which is used for trunking VLANs over a single link. How does this fit in with Linux as i wouldn't have thought a Linux machine can differentiate between 802.1q and non 802.1q frames.
HTH
PJD