Mine for 2016 in Bitcoins! PCG.SE New Year's Puzzle 2016

Mathematica, 94

(For[i=0,IntegerDigits[4Hash[#<>ToString@++i,"SHA256"],64]~SequenceCount~{54,52,53,58}<1,];i)&

This function will try positive integers as candidates. It takes over 4 minutes on my laptop to get the correct answer.

%["foo"]
(* 196870 *)

Longer however faster (~5x) implementation makes use of parallelization:

f[k_]:=
    Do[If[Length@#>0,Return[i+#[[1,1]]]]&@
        Position[ParallelMap[IntegerDigits[4Hash[k<>ToString@#,"SHA256"],64]
            ~SequenceCount~{54,52,53,58}&,i+Range@1*^4],1]
        ,{i,0,∞,1*^4}]

Perl 5.10+, 39 + 18 = 57 bytes

sha256_base64($_.++$i)!~2016?redo:say$i

This needs to be run with the -nMDigest::SHA=/./ command line switch, which is included in the byte count. It also uses the Perl 5.10+ say feature, and so needs to be run with the -M5.010 (or -E) command line switch, which is considered free. The input should be provided on stdin, without a trailing newline (unless you want the newline to be considered part of the input).

Examples:

$ echo -n foo | perl -nMDigest::SHA=/./ -E 'sha256_base64($_.++$i)!~2016?redo:say$i'
196870
$ echo -n bar | perl -nMDigest::SHA=/./ -E 'sha256_base64($_.++$i)!~2016?redo:say$i'
48230
$ echo -n happynewyear | perl -nMDigest::SHA=/./ -E 'sha256_base64($_.++$i)!~2016?redo:say$i'
1740131
$ echo -n 2016 | perl -nMDigest::SHA=/./ -E 'sha256_base64($_.++$i)!~2016?redo:say$i'
494069

Ruby, 87 86 bytes

I'm not sure if I understood the challenge correctly, but it finds 196870 in a few seconds if you input foo.

require"digest"
gets.chop!
$.+=1until/2016/=~Digest::SHA256.base64digest("#$_#$.")
p$.