Null distribution of Blomberg's K
The methods should be equivalent, given the same data. Using phylosignal's demo:

library("picante")
library("phytools")

set.seed(5)
randtree &lt;- rcoal(20)
randtraits &lt;- rTraitCont(randtree)

phylosignal(randtraits[randtree$tip.label],randtree)

phylosig(randtree, randtraits[randtree$tip.label], method="K",test=TRUE)


phylosignal returns:

         K PIC.variance.obs PIC.variance.rnd.mean PIC.variance.P PIC.variance.Z
1 1.430635          0.01147             0.4631411          0.001      -2.662701


and phylosig:

$K
[1] 1.430635

$P
[1] 0.001


Both give K = 1.430635 and an identical P-value. 

Mathematically, it shouldn't matter if you shuffle the trait values or generate a null distribution of K. To get a null distribution for K, you have to shuffle something, and the tip values are probably being shuffled. You could check the code to be sure. An analogy is that, when doing a randomization for an ANOVA-like test, you can either shuffle the observed values or the group membership. Either way will give the same answer.

As for interpretation, Brownian motion is the simplest model for trait evolution, implying no direction, optima, rate changes, etc. K = 1 when the observed variation equals the expected variation. If K is greater than 1 then neighboring tips tend to resemble each other more than you would expect, suggesting a deviation from Brownian motion.