The Nakedness was not merely physical in nature
It's important to note that this is Adam's claim--not God's. Adam and Eve had indeed taken measures to clothe their nakedness after their sin. Before sin, when they were both in a state of innocence, it seems they felt no need for clothing. This is akin to a young child who experiences no shame in being unclothed, much to the chagrin of his parents.
Adam and Eve's clothing appears to have been sufficient in relation to one another. However, as soon as God enters the picture, the insufficiency of their own efforts becomes apparent.
It seems, then, that mankind's efforts to cover over their own sin may be sufficient among others who have sinned, but it is insufficient in the presence of God.
If Adam's nakedness had merely been physical, then physical clothing would have been sufficient to cover over his shame. The shame, however, was not merely physical and neither was his sin. It was also a spiritual act of defiance toward God.
God's Provision
It's interesting to note that later in the chapter, God makes clothing for Adam and Eve. We must wonder what the fig leaves were insufficient and why God considered other clothing to be superior.
The nature of the clothing provided by God is that they were from the skins of an animal. Although this is not explicitly stated, it seems reasonable to conclude that this was the first substitutionary sacrifice. An animal had to die to provide the animal skins for that clothing. The death of the innocent animal was sufficient to cover the shame of sin, yet it was insufficient to atone for the guilt, since Adam and Eve were still banished from the garden.
While the sacrifice of the innocent covered over the shame of sin, it would require the sacrifice of the Righteous One (Jesus) to atone for the guilt.
The physical clothing made by God is then a picture of the spiritual clothing that would be provided through the atoning sacrifice of Jesus Christ.
The New Testament speaks of a type of clothing that comes to followers of Christ:
You are all sons of God through faith in Christ Jesus, for all of
you who were baptized into Christ have clothed yourselves with Christ. Galatians 3:26-27
Now we know that if the earthly tent we live in is destroyed, we have
a building from God, an eternal house in heaven, not built by human
hands. Meanwhile we groan, longing to be clothed with our heavenly
dwelling, because when we are clothed, we will not be found naked. For
while we are in this tent, we groan and are burdened, because we do
not wish to be unclothed but to be clothed with our heavenly dwelling,
so that what is mortal may be swallowed up by life. 2 Corinthians
5:1-2
So, Adam was not naked at that time in a physical sense, but he was still naked (exposed, in a state of shame) in a spiritual sense.
