How do i make my local script run when a specific player sends a specific message?

Connect the function to Player.Chatted event, where the first parameter is the message of the player who chatted.

NOTE: Changing a property in a LocalScript will not cause any changes on the server, thus other clients can't see that the BrickColor of the part has been changed. Also, BrickColor is not a property of Workspace.

To make it work in a LocalScript, first you have to specify who would you like to check. Then create a Chatted event to their Player object in order to check if the specified player is sending the corresponding message.

Here's the full demonstration on how to use it:

--You can try playing with this LocalScript, but with a few modifications to fulfill your needs.
--Unless that, consider this is just a reference
local plrs = game.Players
local localplr = plrs.LocalPlayer

local name = "NotKeanuReeves" --Can be any name of any players.
-- In case if YOU are the sender, set this field to localplr.Name
-- In another case if you don't know the name of the target, you can try indexing the Player list using a for loop, then pick a player under certain conditions, then get their name, or just simply get their player object and set it in a precreated variable.

local plr = game.Players[name] --Get their player object using the name of the player

plr.Chatted:Connect(function(msg)
    if msg == "you big noob" then --check if player is sending the correct message
        workspace.PartToChangeColor.BrickColor = BrickColor.Random() -- then do your thing. Also, "workspace" here is a global namespace that works just like game.Workspace.
    end
end)

--end of story