It also depends on how you learn it, and who you learn it from. The pickax book is a fantastic book for learning ruby. Same goes for Learning Perl for perl. I've never seen a similar book for Python, but one might exist? For JavaScript you cannot beat Douglas Crockford's videos at the Yahoo! Developer Network. Absolutely fantastic...taught me everything I needed to know to be productive in the language in one weekend. JavaScript also happens to be a great learning language, as it has both functional and imperative constructs and pretty simple syntax and minimal keywords.
Find all of them (along with a few other good ones--Joe Hewitt's Firebug demo, in particular, is what you'll want after the Crockford vids) here:
I haven't found anything yet, though, on advanced techniques or how to write "pythonic" code. I decided to start reading "On Lisp," instead.
http://safari.oreilly.com/0672328623 (Beazley's Python reference)
But learning syntax and libraries is much different than (for lack of a better word) learning the "zen" of it. You could learn python and just write C-style code in it in a few hours, but it might take much much longer to change the way you look at and solve problems to match the strengths of a language.
Then there is the long process learning the right idioms, keeping up with the latest changes in newer languages, familiarizing yourself with the universe of libraries, etc, etc - I think all of these things are required to really claim fluency in a language. So I would answer "a long, long ass time."
Code from those early days of basic literacy are the thoughest to look back on. "Hey, why does this perl code look like it is trying to be C++?"
[edit] I second far33d. You can write FORTRAN in any language. :) Each language has its own conceptual style, idioms, and so on. Learning how to think in a language is real fluency.
I learned Python so quickly, I used to stare at the 2 lines I'd just written that did the same work as 20 in C++. My brain had to play catch-up since it was used to autopiloting while filling in the tedium.
As for how long with a new language: speaking without quantitative data, I'd say differences in motivation are much larger than differences in languages, for languages with a reasonable set of libraries (i.e. brainfuck and the like excluded).
Learning the idioms? A month.
Mastery? Heck, I've been programming in C for 15 years and Perl for 10, and I don't think I'm a master in either.
And at this point I can pick up a new language (Javascript, say, which is my current sort-of project) and it's just a matter of learning syntax because I've used that concept in another language before.
Even if you took the average I don't know if it would lead to a useful statistic.
My own estimate would be about a week (I can program after a few hours of course, but not with as much confidence as after a week).
Haskell is still kicking my ass after six weeks of spare-time though, so I think it has more to do with the language than anything.