Butter may look totally amorphous, but there's actually a fair amount of structure in the fat, in particular fat crystals that make it firmer. Melting it disrupts all that structure, and it can't regain it just by resolidifying, so the structure of previously melted butter really is different.
You might notice that this is similar to chocolate: if you take smooth, snappy tempered chocolate, melt it, and let it resolidify, the texture will often be grainy, soft, or even crumbly. That's also thanks to fat crystals, in that case in the cocoa butter.
To back up a bit, let's look at how butter is made. Churning is the most well-known step, but there's more:
Aging (heating, cooling, and storing the cream). The cream is heated and cooled, with resting periods at various temperatures, which encourages formation of certain kinds of fat crystals. (The details of this process vary; for example different temperatures can be used depending on the hardness of the milkfat.)
Churning. This damages the fat globules, causing them to release fat, which forms much of the mass of the butter and lets it collect into grains.
Working/kneading. After draining off the buttermilk, the grains are kneaded together. This evens out small amounts of buttermilk trapped in the grains, and fat crystals can also come together into larger networks.
So the final butter actually has three forms of fat in it: fat crystals, free fat, and fat globules. The fat crystals make it firmer, and the free fat and globules make it softer. This also explains why butter isn't all the same texture. For example, from On Food and Cooking:
Feeds rich in polyunsaturated fats, especially fresh pasturage, produce softer butters; hay and grain harder ones. The butter maker also influences consistency by the rate and degree of cooling to which he subjects the cream during the aging period, and by how extensively he works the new butter. These conditions control the relative proportions of firming crystalline fat and softening globular and free fat.
So when you melt and resolidify butter, it's not just a simple solid to liquid to solid thing. You're disrupting the crystals, and potentially even rupturing a few more fat globules. That means a couple things:
There's likely more free fat and less crystals, which explains why previously melted butter can be much softer than the original butter.
The crystals that do remain or reform won't have the same structure as the original ones, since you didn't follow the same heating/cooling/storing regimen. That explains the graininess you noticed. It's possible that working/kneading the butter might even that back out to some extent.
The exact texture of your previously melted butter will probably vary, depending on how hot you melted it and how fast you cooled it afterwards.