This isn't a Rails problem, it's something that happens in Ruby. I think it's a bug:
$ irb -r date
irb(main):001:0> format = "%m/%d/%Y"
ArgumentError: invalid date
from (irb):2:in `parse'
from /Users/tamara/.rubies/ruby-2.0.0-p427/bin/irb:12:in `<main>'
=> #<Date: 2013-08-18 ((2456523j,0s,0n),+0s,2299161j)>
$ ruby -v
ruby 2.0.0p247 (2013-06-27 revision 41674) [x86_64-darwin12.4.0]
I don't have anything older to check this on, however, reading the system documentation for strptime(), it seems to state that formats should be compatible with strftime().
A quick test in C shows that the format from strftime to strptime is compatible. So sounds like a ruby bug…