When I look at the statistics, the pull from Flickr seems to be quite quick – it takes less than 1 s for the entire cycle to make the call to Flickr, process the response and generate the markup (this information is printed when you enable performance logging). On your browser each photo by itself seems to be taking around 50-60 ms to fetch, and it is happening in parallel – this is evidenced by the very short amount of time that you see the “spinning” icon when your page renders.
Also, when I look at the requests made by your site, it looks like fetching the first byte itself is taking the longest (> 1.3 min), so this is likely to be a performance issue with your hosting, where WP is taking quite long to generate the contents of a page and serve the output. For your other pages this seems to be less of an issue because it appears that you have those pages cached (the pages are served from cache, so WP is not having to generate anything on the fly). What type of hosting are you using?
How dynamic is your photostream? Is there a possibility of you being able to cache some of these pages? Short of caching I don’t see a way out if the hosting is slow.