I’m having a similar issue with WordPress 3.4.1 on an EC2 server with PHP 5.3.14. On 2 separate projects I’ve had issues not with shortcodes not working at all, but rather with them not parsing arguments correctly.
I spent a lot of time looking in to it last night and it turned out to be this line of code in /wp-includes/shortcodes.php in the shortcode_parse_atts() function:
$text = preg_replace("/[\x{00a0}\x{200b}]+/u", " ", $text);
In my staging environment this replace is essentially wiping out all of the shortcode arguments. Commenting it out fixes the problem. I’ve found this issue discussed in several other places but none include a solution.
If there’s anything else I can provide that can help figure this one out let me know.