DBCC CLEANTABLE is not freeing used space

Question

I have about 300 tables with 5.5kk rows each. One of the rows is using nvarchar(128) as a datatype (SQL Server 2012).
We decided to change this to int and add FK to dictionary table with all nvarchars.

After doing all of it I removed the nvarchar column, but the size of the tables remained the same. I used DBCC CLEANTABLE and rebuilt the indexes to reclaim free space, but size of the table is still not changing.

So far, the only way I found is to copy all data to the new table.

Question: What am I missing here ? Why the space is still marked as used and I can't free is by shrinking or CREANTABLE command?

Thank you!

Answ: Looks like the answer was pretty simple and I was not able to find it due to my lack of knowledge. The main problem here was heap fragmentation. This query worked for me:

ALTER TABLE [TABLE_NAME] REBUILD

I am not sure that it's the best way, but at least it's a working one.

Edited1: Sorry, I think I forgot to mention - I had clustered index on the Text field, so I had to remove the index to be able to actually remove the field. Now I have no indexes.

Edited2:

old table:

CREATE TABLE [dbo].[Data_](
    [ID] [bigint] PRIMARY KEY IDENTITY(1,1) NOT NULL,
    [Text] [nvarchar](128) NOT NULL,
    [Category] [tinyint] NOT NULL,
    [Country] [nvarchar](2) NOT NULL,
    [ImportTimestamp] [date] NOT NULL
)

new table:

CREATE TABLE [dbo].[Data_New](
    [ID] [int] PRIMARY KEY IDENTITY(1,1) NOT NULL,
    [Category] [tinyint] NOT NULL,
    [Country] [nvarchar](2) NOT NULL,
    [TextID] [int] NOT NULL)

ALTER TABLE [dbo].[Data_New]  WITH CHECK ADD FOREIGN KEY([TextID])
REFERENCES [dbo].[Dictionary] ([Id])

Copy script:

INSERT INTO Data_New
      ([Category]
      ,[Country]
      ,[TextID])
SELECT 
      [Category]
      ,[Country]
      ,[TextID]
  FROM Data_

Answer 1

If you don't care about understanding the issue and just want to get rid of it then rebuilding the index is a sure way to remove any waste. This is because a index rebuild constructs the physical data structures freshly. Whatever the old index contained will not matter anymore.

There are trade-offs involved when comparing this with CLEANTABLE. If a rebuild does the job for you I'd always do that because it is such a complete solution.

When I say "index" in this answer I mean all physical structures that contain one of the columns you care about. That can be b-tree indexes or the heap the table is based on.